Reputation: 1222
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
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
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