CODEWITHSUNDEEP
c
Sam
Sam

Reputation: 11

Sort an array based on an index array in C

I am trying to sort many arrays in parallel. I sort one array by qsort and I return an int array which specifies the indices of their original positions. Now with this int array, I need to sort other arrays.

Array 1:

 zzz
 yyy
 def
 abc
 cde
 xxx

after sorting, I get the index array and the sorted array:Idx position array

3   :    abc
4   :    cde
2   :    def
5   :    xxx
1   :    yyy
0   :    zzz

Now based on this index array, I need to sort another array

a
b
c
d
e
f

so that it becomes

d
e
c
f
b
a

Thanks a lot

Upvotes: 1

Views: 1455

Answers (2)

elcuco
elcuco

Reputation: 9208

This code here shows two ways of doing this:

The first way does it using a qsort().. in pure C but consumes a little more memory

struct pair {
    int distance;
    int index;
};

int my_pair_compare(const void *const first, const void *const second)
{
    const pair* a = (const pair*)first;
    const pair* b = (const pair*)second;
    if (a->distance > b->distance)
       return 1;
    else if (a->distance < b->distance)
        return -1;
    else
        return 0;
}

void calculate_new_order1(int week_count, float distances[], int new_order[])
{
    struct pair ab[week_count];
    for (int i = 0; i<week_count; ++i) {
        ab[i].distance = distances[i];
        ab[i].index = i;
    }
    qsort(ab, week_count, sizeof(*ab), my_pair_compare);
    for (int i=0; i<week_count; ++i){
        new_order[i] = ab[i].index;
    }
}

The seconds saves the distances (in my example) into a map, and then iterates over the map. A C++ way.

void calculate_new_order2(int week_count, float distances[], int new_order[])
{
    std::map<float,int> ooo;
    for (int week=0; week<week_count; week++) {
        ooo[distances[week]] = week;
    }
    int t = 0;
    for (auto i=ooo.begin(); i!=ooo.end(); i++) {
        new_order[t] = i->second;
        t++;
    }
}

The problem with the second solution is that if you have two "weeks" with the same distance, this will fail, as the values are saved into the same map index.

Upvotes: 1

Erik
Erik

Reputation: 91320

for (i=0; i < 6; ++i)
  SortedArray[IndexArray[i]] = AnotherArray[i];

Upvotes: 2

Related Questions