Sort an array based on members of another array in C++

Pau picture Pau · May 14, 2012 · Viewed 9.3k times · Source

my problem is the next (is an easy example to show the problem):

I have:

int* array1;
double* array2. 

array1=new int[10];
array2=new double[10];
array1=filledWithIntegers(random);
array2=filledWithDoubles(random);

//Here I want to sort array1 based on array2 values. I´m trying to use qsort function of stdlib. qsort(array1,6, sizeof(int), compare);

The point is how to make the compare function for order array1 based on array2.

It is not possible to use std library data structures, it must be done directly in the array pointers.

Thanks.

Answer

Sergey Kalinichenko picture Sergey Kalinichenko · May 14, 2012

Instead of sorting integers of array1, sort their indexes using array2[index] to compare items, and then re-arrange array1 in accordance with the permutation that you get back from the sort.

Here is a quick demo:

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

int array1[] = {1, 7, 3, 9, 5};
double array2[] = {1.1, 7.7, 3.3, 9.9, 5.5};

int compare (const void * a, const void * b) {
    double diff = array2[*(int*)a] - array2[*(int*)b];
    return  (0 < diff) - (diff < 0);
}

int main(void) {
    int perm[5], i;
    int res[5];
    for (i = 0 ; i != 5 ; i++) {
        perm[i] = i;
    }
    qsort (perm, 5, sizeof(int), compare);
    for (i = 0 ; i != 5 ; i++) {
        res[i] = array1[perm[i]];
    }
    for (i = 0 ; i != 5 ; i++) {
        printf("%d\n", res[i]);
    }
    return 0;
}