keeping track of the original indices of an array after sorting in C

Question

I have an array let's say A[5], the 5 elements are 5,4,1,2,3. Now I sort these arrays in ascending order. so the resulting array will now be 1,2,3,4,5. I use qsort() function of stdlib.h to sort this. The question is how can I get the indices of the original array with respect to my new array. originally my indices were 0,1,2,3,4 for corresponding values of 5,4,1,2,3 and now the indices have changed to 2,3,4,1,0. How can I get these indices efficiently in C? Thank you in advance(please write the code if possible)

Answer 1

There is also a method as follows under limited conditions.

#include <stdio.h>

int main(void){
    int data[] ={ 5,4,1,2,3 }; //Without duplication, The number of limited range.
    int size = sizeof(data)/sizeof(*data);
    int keys[size];
    int i;

    printf("data :\n");
    for(i=0;i<size;i++){
        printf("%d ",data[i]);
    }
    for(i=0;i<size;i++){
        keys[data[i]-1]=i;
    }

    printf("\n\ndata\tindex\n");
    for(i=0;i<size;i++){
        printf("%d\t%d\n", data[keys[i]], keys[i]);
    }
    return 0;
}
/* result sample
data :
5 4 1 2 3

data    index
1       2
2       3
3       4
4       1
5       0
*/

---

How to sort an array of index @Kerrek is as proposed.

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

int *array;

int cmp(const void *a, const void *b){
    int ia = *(int *)a;
    int ib = *(int *)b;
    return array[ia] < array[ib] ? -1 : array[ia] > array[ib];
}

int main(void){
    int data[] ={ 5,4,1,2,3 };
    int size = sizeof(data)/sizeof(*data);
    int index[size];//use malloc to large size array
    int i;

    for(i=0;i<size;i++){
        index[i] = i;
    }
    array = data;
    qsort(index, size, sizeof(*index), cmp);
    printf("\n\ndata\tindex\n");
    for(i=0;i<size;i++){
        printf("%d\t%d\n", data[index[i]], index[i]);
    }
    return 0;
}

Answer 2

Take a 2D array. Store the numbers is first column and then corressponding indexes in second column. You can write your comparator function as:

int compare ( const void *pa, const void *pb ) 
{
    const int *a = pa;
    const int *b = pb;
    if(a[0] == b[0])
        return a[1] - b[1];
    else
        return a[0] - b[0];
}  

Call to qsort should be:

qsort(array, n, sizeof array[0], compare);  // n is representing rows  

See the Live Demo

Answer 3

#include <limits.h>
#include <stdio.h>
#define SIZE 5
int* sortArrayNKeepIndices(int arr[], int arrSize){
    static int indexArr[SIZE];
    int arr2[arrSize];
    for (int i = 0; i < arrSize; i++) {
        indexArr[i] = 0;
        arr2[i] = arr[i];
    }
    int min = 0, temp = 0;

    for (int i = 0; i < arrSize ; i++)
    {
        min = i;  // record the position of the smallest
        for (int j = i + 1; j < arrSize; j++)
        {
            // update min when finding a smaller element
            if (arr[j] < arr[min])
                min = j;
        }
        // put the smallest element at position i
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    } // array sorting ends here
    int ctr = 0;
    while ( ctr < arrSize) {
        min = 0;  // restart from first element
        for (int j = 0; j < arrSize; j++)
        {
            if (arr2[j] == INT_MAX) continue; // ignore already marked as minimum indices
            // update min when finding a smaller element
            if (arr2[j] < arr2[min])
                min = j;
        }
        indexArr[ctr] = min; // updating indexArr with the index of the next minimum
        arr2[min] = INT_MAX; // marking minimum element to be ignored next time
        ctr++;
    } //keeping track of previous indices of the array elements ends here
    return indexArr;
} // function sortArrayKeepIndices ends here
int main () {
    int arr[SIZE] = {16, 15, 12, 10, 13};
    int* ptr = sortArrayNKeepIndices(arr, SIZE);
    for (int dex = 0; dex < SIZE; dex++){
        printf("%d (%d, %d)\t", arr[dex], * (ptr + dex), dex);}
}

// output will be 10 (3, 0) 12 (2, 1) 13 (4, 2) 15 (1, 3) 16 (0, 4) // element (old index, new index)