Sort an array of arrays by various indices in C

Question

Let's say I have a set of data points that are represented as an array of doubles arrays, so

double **data; 

Now, if I wanted to sort the data by a field in each of the data points, say, in field 2 ^nd, I would write a comparator that would do something like:

 int compare_data_second_field(void *a, void *b) { double da = ((double *) a)[1]; double db = ((double *) b)[1]; if (da < db) return -1; else if (da > db) return 1; return 0; } 

and then use qsort to sort them by 2 ^nd field.

My question is: how did I generalize this if I don’t know which field I want to sort before? For example, I can sometimes sort field 1 ^st and field 5 ^th , etc. I would also like it to be thread safe, so I don’t want to use a global variable to keep track of which field to sort, since several of them can go right away.

In C ++, I would just use my own sort class and have an instance variable in the class to keep track of which field to sort. I don't know how to do something like this in C.

Answer 1

A better way would be to use qsort_r if it is available on your platform. qsort_r takes an additional argument, which is passed to your comparator, so you can use it to pass the field by which you want to sort your data.

If this is not available on your platform, then there really is no easy way to do this. You can get around this by using global variables by wrapping your data in a structure that will contain information about the sort field, or by flipping your own qsort_r like function.

Answer 2

Actually there is a pretty neat solution for this with nested functions (which are an extension of GCC).
What you can do is make a general comparator:

 int my_comparator(const void* a, const void* b, int n) { double da = ((double*)a)[n]; double db = ((double*)b)[n]; return (da > db) ? 1 : ((da < db) ? -1 : 0); /* Awesome */ } 

and a custom sort function that wraps the original qsort() :

 void my_qsort(void* base, size_t num, size_t size, int (*comparator)(const void *, const void *, int), int field) { /* Internal comperator */ int my_qsort_comperator(const void* a, const void* b) { return comparator(a, b, field); } /* Invoke the base qsort function */ qsort(base, num, size, my_qsort_comperator); } 

This function behaves the same as the original qsort() , except that it requires an additional field argument, which indicates the index of the field to sort.

Answer 3

You can declare a whole bunch of compare_data_field_N functions for N = 0,1,2 ... and then declare an array of compare_data function pointers initialized with the corresponding functions. Then, for qsort in a specific field, you pull the function pointer from the array to go to qsort. You can use macros to simplify function and array generation:

 #define REP10(M) M(0) M(1) M(2) M(3) M(4) M(5) M(6) M(7) M(8) M(9) #define DECLARE_COMPARE(N) \ int compare_data_field_##N(void *a, void *b) { \ double da = ((double *) a)[N]; \ double db = ((double *) b)[N]; \ if (da < db) return -1; \ else if (da > db) return 1; \ return 0; \ } #define REF_COMPARE(N) compare_data_field_##N, REP10(DECLARE_COMPARE) int (*compare_data_field[])(void *, void *) = { REP10(REF_COMPARE) }; 

You only need to modify the REP10 macro if you want more than 10 potential fields.