CODEWITHSUNDEEP
csortingstructure
nurabha
nurabha

Reputation: 1222

Sorting structure of arrays with qsort

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!

Upvotes: 4

Views: 2506

Answers (2)

Jason
Jason

Reputation: 1069

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.

Upvotes: 0

Shahbaz
Shahbaz

Reputation: 47603

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.

Upvotes: 1

Related Questions