12

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.

Pau
  • 125
  • 1
  • 1
  • 8

3 Answers3

8

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;
}
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    Almost. `compare` should return `-1` (instead of `0`) when smaller. – user2k5 May 14 '12 at 14:20
  • @user2k5 You're right - I changed the function to use the sign trick from [this answer](http://stackoverflow.com/a/4609795/335858). – Sergey Kalinichenko May 14 '12 at 14:26
  • 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. – Christian Rau May 14 '12 at 14:38
  • Thanks for your answer @dasblinkenlight your solution has been a valid one for my problem. – Pau May 14 '12 at 14:49
3

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);
}
guinny
  • 1,522
  • 10
  • 19
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.

Christian Rau
  • 45,360
  • 10
  • 108
  • 185
  • thanks for taking your time to answer, i got a solution in a previous one. – Pau May 14 '12 at 14:56
  • 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??! – ahmed allam Dec 10 '20 at 02:25
  • 1
    @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`. – Christian Rau Dec 10 '20 at 15:59