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

Based on Kerrek SB's brilliant idea I made an implementation that works for any array type by providing its element size and a comparator function for that type.

_Thread_local uint8_t *array_to_order;
_Thread_local size_t elem_size_to_order;
_Thread_local int (*cmp_for_ordering)(const void *, const void *);

int cmp_array_entry(const size_t *a, const size_t *b)
{
    return cmp_for_ordering(&array_to_order[*a * elem_size_to_order], &array_to_order[*b * elem_size_to_order]);
}

size_t *make_order_index_array(void *array, size_t *order, size_t elem_count, size_t elem_size, int (*cmp)(const void *, const void *))
{
    // If order is provided by the caller it should have suitable contents, such as when updating an order

    // Initialise the order array if not already provided
    if (order == NULL)
    {
        order = calloc(elem_count, sizeof(size_t));

        // Initialise the order array to the unsorted indices
        for (size_t i=0; i < elem_count; i++)
            order[i] = i;
    }

    // Globals used by the comparison function to order the array
    array_to_order = array;
    elem_size_to_order = elem_size;
    cmp_for_ordering = cmp;

    // Order the order array
    qsort(order, elem_count, sizeof(size_t), cmp_array_entry);

    return order;
}

_Thread_local is something that we should be able to take for granted for writing such code when we're forced to use globals but should worry about thread safety. Mine is defined with the following macros:

#if defined(_MSC_VER) && !defined(_Thread_local)
    #define _Thread_local __declspec(thread)
#endif

#if !(defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201102L)) && !defined(_Thread_local)
    #if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__SUNPRO_CC) || defined(__IBMCPP__)
        #define _Thread_local __thread
    #endif
#elif defined(__GNUC__) && defined(__GNUC_MINOR__) && (((__GNUC__ << 8) | __GNUC_MINOR__) < ((4 << 8) | 9))
    #define _Thread_local __thread
#endif

Answer 4

#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)