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.

Movement

Answer 1

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

Indrawn

Almost. compare should return -1 (instead of 0) when smaller. – Darees

@Darees You're right - I changed the function to use the sign trick from this answer. – Indrawn

No need for an additional permutation array, just compute a's and b's positions inside array1. The comparator already has to know array2, anyway. – Hajji

Thanks for your answer @dasblinkenlight your solution has been a valid one for my problem. – Movement

Answer 2

yes. You need to group the two arrays into one array of pair, and then define the compare function.

the compare function could be:

bool compare(const pair<int,double>& t1, const pair<int,double>& t2){
    return (t1.second < t2.second);
}

Underpin

Thanks for your answer. I forgot to tell that it is not a possibility using std library types, only sort the array pointer values trying to preserve the format of the data – Movement

then you could define the map yourself using struct? – Underpin

Could it be you mean pair instead of map? – Hajji

Thanks for taking your time answering, i got the solution with the previous reply. – Movement

Answer 3

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.

Hajji

thanks for taking your time to answer, i got a solution in a previous one. – Movement

I can not understand the first 2 lines in your code: how do you subtract array1"it is pointer" from another pointer in another array??! – Antonia

@ahmedallam Subtracting two pointers gives you the distance between the elements they point to. As long as both pointers point into the same array, this is perfectly standard-conformant behaviour. And the specific call to qsort in turn guarantees that a and b both point into array1. So all that does is compute the indices inside array1 that a and b point to, which are then used to index array2. – Hajji