Sorting structure of arrays with qsort

Question

Normally sorting Array of structure objects is easy. Consider an Array of a structure (AOS)

#define ITEMS 10

typedef struct MyStruct
{
 char a;
 int  b;
}tMyStruct;

tMyStruct arr_mystruct[ITEMS];

I first fill this array of structure with values of < a , b> pairs.

If I now want to sort this array of structures according to the integer field, I can do it using libc qsort function by using a comparison function which takes two integer arguments.

Now consider that I replace the above structure in AOS format with SOA format

#define ITEMS 10

typedef struct MyStruct
{
 char a[ITEMS];
 int  b[ITEMS];
}tMyStruct;

tMyStruct mystruct;

Now I can still use qsort to sort the array of integers b field, however this time I need to additionally sort a (array of characters) w.r.t sorting order of b.

So my question is what is a possible efficient way to do sorting for data laid out in SOA format instead of usual AOS format?

Can anyone help me with this ? Thanks!

a w.r.t sorting order of b. Can you please translate this one for me... — nullpotent
– nullpotent, Commented Jul 27, 2012 at 15:28
I think he wants to sort the arrays a and b so that they are both sorted according to b's data. In other words, keep all the pairs of data together. — crashmstr
– crashmstr, Commented Jul 27, 2012 at 15:29
You've tagged this with C++, are you interested in C++ solutions? Ones that won't work in C? — Benjamin Lindley
– Benjamin Lindley, Commented Jul 27, 2012 at 15:39
If std::sort only works by means of std::less and std::swap, then you could solve your problem by providing a custom std::swap which takes care of as as well. Otherwise there are really no "good" solutions. — akappa
– akappa, Commented Jul 27, 2012 at 15:48

Shahbaz · Accepted Answer · 2012-07-27 15:43:47Z

1

Probably the best way would be to use a helper array:

int helper[ITEMS];

int helper_cmp(const void *a, const void *b);

for (i = 0; i < ITEMS; ++i)
    helper[i] = i;
qsort(helper, ITEMS, sizeof(*helper), helper_cmp);

The helper_cmp function will take helper values as indices to mystruct.b and compares those values:

int helper_cmp(const void *a, const void *b)
{
    int first = *(const int *)a;
    int second = *(const int *)b;
    int b_first = mystruct.b[first];
    int b_second = mystruct.b[second];
    // compare b_first and b_second
}

Then, after the qsort, the helper array will contain rearranged indices of b, telling how it should be ordered.

You can use this array to both rearrange mystruct.a and mystruct.b.

Note that this is not as efficient as sorting "array of struct". I don't know your application, but my guess is that "struct of array", in which the fields of the arrays are correlated is not a good idea in the first place. That is, if sorting of b affects sorting of a, they probably belong to the same conceptual element (call it class if you want), and it is better if they are grouped together in one struct.

edited Jul 27, 2012 at 15:43

answered Jul 27, 2012 at 15:34

Shahbaz

47.8k19 gold badges120 silver badges187 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

nurabha Over a year ago

SOA approach is frequently used optimization in multi-cores (SIMDization, cache efficiency) and GPU(CUDA).

Jason · Accepted Answer · 2012-08-01 00:13:43Z

0

Other than the helper suggestion, there isn't a way to do this with qsort(). For a case like this, I would write my own sorting function. For best balance of speed and easy-to-write I find that Insertion Sort works well for small arrays and Merge Sort works well for large arrays.

answered Aug 1, 2012 at 0:13

Jason

1,08910 silver badges13 bronze badges

Collectives™ on Stack Overflow

Sorting structure of arrays with qsort

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related