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

Question

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 1

Well, you just have to use the position of the elements to index the other array in your comparision function (the standard guarantees that the pointer arguments of the comparison function always point into the to be sorted array):

int compare(const void *a, const void *b)
{
    unsigned int i = (const int*)a - array1;
    unsigned int j = (const int*)b - array1;
    if(array2[i] < array2[j])
        return -1;
    if(array2[i] > array2[j])
        return 1;
    return 0;
}

The disadvantage is, that the comparison function explicitly needs to know the specific arrays, as it cannot take any additional parameters.

I would question the use of qsort anyway, since your question is tagged C++. Although std::sort has the same problem, you can reach much more genericity/abstraction by using a comparison functor that encapsulates the depending arrays.

Answer 2

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;
}