keeping track of the original indices of an array after sorting in C
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)
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;
}
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