Улучшенная функция qsort() в c

Question

Предположим, что мы сортируем 1D-массив с помощью qsort(), есть ли простой способ получить из элемента отсортированного массива индекс, который был очень элементом, когда он был проиндексирован в массиве прежде чем он будет отсортирован. Скажем, c [N] сортируются как d [N], как найти из целого числа i, j такое, что c [j] = d [i]? Когда я имею в виду простой способ, qsort (с некоторым дополнительным параметром) хранит эту информацию (биекция между индексацией до сортировки) или существует ли функция qsort, которая могла бы сортировать и извлекать легко такую ​​информацию?

Answer 1

Предполагая, что вы заполнить исходный массив со структурой, как это:

struct IndexedInteger { 
    int value; 
    int index; 
} 

Затем нужно будет заполнить индексы в цикле:

void addIndices(IndexedInteger * array, size_t num) { 
    int i; 
    for (i = 0; i < num; ++i) { 
    array[i].index = i; 
    } 
} 

Тогда вы будете сортировать массив:

int compareIndexed(const void * elem1, const void * elem2) { 
    IndexedInteger * i1, *i2; 
    i1 = (IndexedInteger*)elem1; 
    i2 = (IndexedInteger*)elem2; 
    return i1->value - i2->value; 
} 

void sortArray(IndexedInteger * array, size_t num) { 
    qsort(array, num, sizeof(IndexedInteger), compareIndexed); 
} 

Затем вы будете отсортированы по вашему массиву с начальными показателями.

Отказ от ответственности: Я пишу это довольно быстро, могут быть ошибки.

Answer 2

Что вы можете сделать, это создать struct, в котором хранятся ваши данные (в данном случае целое число), а также целое число, соответствующее индексу позиции, где оно было первоначально на вашем массиве. Чтобы уточнить,

#include <stdio.h> 
#include <stdlib.h> 

struct myData { 
    int data; 
    int orig_pos; // will hold the original position of data on your array 
}; 

int myData_compare (const void* a, const void* b) { 

    return ((struct myData*)a)->data - ((struct myData*)b)->data; 
} 

int main() { 

    size_t N = 10; // size of your array 
    struct myData* array = (struct myData*) malloc(N * sizeof(struct myData)); 
    for (size_t i = 0; i < N; i++) { 
     array[i].data  = N - i; // array will hold 10,9,8,7,...1 in this order 
     array[i].orig_pos = i; 
    } 
    qsort(array, N, sizeof(struct myData), &myData_compare); 
    for (size_t i = 0; i < N; i++) { 
     printf("\ndata: %d, orig_pos: %d", array[i].data, array[i].orig_pos); 
    } 
    return 0; 
}