[Solved] Sorting an array without losing the original index in C [closed]

by


Since this is C and not C++, you’ll need to create your own sort program since I think qsort() can be O(n^2) worst case.

Since you will be using your own sort program, you could just sort the array and the indices at the same time, treating them as pairs of elements.

If there was an existing O(n log(n)) sort function that you could call, you could create an array of indices 0 to length-1, and sort the array of indices according to the array, then copy the array to a temp array according to the sorted indices, then copy the temp array back to the original array.

void rem_sort(int array[], int index[], int size){
    /* temp array */
    int * tmpa = malloc(size * sizeof(array[0]));
    int i;
    /* generate indices to array */
    for(i = 0; i < size; i++)
        index[i] = i;
    /* sort index according to array in O(n log(n)) time */
    sort(array, index, size);
    /* tmpa[] = sorted array[] */
    for(i = 0; i < size; i++)
        tmpa[i] = array[index[i]];
    /* copy tmpa to array */
    for(i = 0; i < size; i++)
        array[i] = tmpa[i];
    free(tmpa);
    return;
}

1

solved Sorting an array without losing the original index in C [closed]