Sorting 2d array with qsort, keeping rows in order (C)

[Mute]

I have been trying to get qsort to sort the rows of a 2d array I read in from a data file, and I have not been having much success to get it to do what I want.

My array is a 4xarraysize array, where arraysize is the number of columns read in from a data file, with four entrees per row. I would like to sort the rows as a whole based on the first two columns: the first column should be sorted in ascending order, but contains many duplicate values, so the sorting should also end with the second row being in ascending order. No sorting within the rows should take place. For an example, if my array were

0.002 365 7.333213e-03 3.385813e-02
0.019 689 3.272068e-02 2.226685e-01
0.008 259 5.767495e-02 1.144423e-01
0.002 2 6.409854e-04 -2.186733e-05
0.017 233 6.801931e-02 2.005469e-01

then upon sorting it should be

0.002 2 6.409854e-04 -2.186733e-05
0.002 365 7.333213e-03 3.385813e-02
0.008 259 5.767495e-02 1.144423e-01
0.017 233 6.801931e-02 2.005469e-01
0.019 689 3.272068e-02 2.226685e-01

i.e., the entire row is moved, ordered based first on the first column and then based on the second column if two entrees of the first column are the same. No two rows will have the same pair of numbers in the first and second row, so sorting based on the third or fourth column is unnecessary.

My data is read in from a file and placed into an array array[4][arraysize], where the number of columns, arraysize, is determined by counting the number of columns in the input file.

The program calls qsort

qsort(&array[0][0], arraysize, 4*sizeof(double), comparefun2);

and I have tried many different combinations of the second and third arguments ({arraysize, sizeof(double)}, {arraysize*4,sizeof(double)}, {arraysize, 2*sizeof(double)}, but no avail - none of them are giving the desired output and it is getting to the point where I think the error is simply that I don't really know quite how qsort is trying to work and I'm feeding it the wrong sizes and/or compare function.

My compare function is

int comparefun2(const void* a, const void* b) {

  double* da = (double*)a;

  double* db = (double*)b;

  int diff1 = (da[0] > db[0]) - (da[0] < db[0]);

  if (diff1 != 0) return diff1;

  return (da[1] > db[1]) - (da[1] < db[1]);

}

The idea is that it compares the entrees of the elements it is given from the first column (which is why I though that the arguments to qsort should be arraysize, the size of the column, and 4*sizeof(double), so that it skips over the rest of the row and only looks at the first column), and if those are unequal, it sorts them, but if they are equal it looks at the entrees of the second column and sorts based on them.

I got this compare function (modified slightly) from a help post on the internet which seemed like the poster wanted to do the same thing, and supposedly it worked for them, but it's not doing what I want. Furthermore, I don't see how this sort of compare function will preserve the entire row. I feel like it doesn't, but I'm not sure how to fix that.

Any help will be appreciated!

 

[rcgldr]

This is an issue with quick sort, it doesn't preserve the original order for "equal" records (rows in your case). A merge sort (and some other sorts) don't have this problem. If you switched to using the Standard Template Library, use stable_sort() instead of sort(). In the case of Visual Studio, stable_sort() creates groups of 32 elements using insertion sort, then switches to merge sort. Visual Studio's sort() is quick sort.

The other solution is to include the original record number as the least significant column (as if it was a third column) for comparing rows, this would force the order to be preserved. You'd have to effectively add original row numbers to the rows.

 

[Mute]

Thanks for the advice. In the end I was convinced by an office-mate to try defining a struct and making a 1d array of structs. It worked like a charm with qsort.

 

[rcgldr]

In the end I was convinced by an office-mate to try defining a struct and making a 1d array of structs. It worked like a charm with qsort.

The alternative would have been to make a 1d array of pointers to each row and sort the pointers. The compare function could include the pointer values as the "third" column if you wanted to preserve the original order when the first two columns are equal (which doesn't happen in your example). I'm not sure why your original code exeample didn't work, since you set the element size to 4 * sizeof(double).

 

[MisterX]

My data is read in from a file and placed into an array array[4][arraysize], where the number of columns, arraysize, is determined by counting the number of columns in the input file.

This seems wrong. The rest of the post seems to indicate there would always be 4 columns. To use qsort you should declare the array thusly:

double array[arraysize][4]

So that each set of four doubles would be in a contiguous block of memory. The way you've declared it the 4 doubles that go together would be separated in memory by arraysize*sizeof(double), which preclude using quicksort, as the collection of doubles would not be able to be swaped as one block of memory.

One potential problem I was able to spot with comparefun2 is there is an assumption that a comparison that evaluates to true would evaluate to a specific positive integer. But AFAIK, such a compairson might evaluate to any non-zero integer.

This is an issue with quick sort, it doesn't preserve the original order for "equal" records (rows in your case).

No, this is not the problem.

One solution to this problem would be to sort twice, first based on the second column, and then based on the first. If this was done, than a stable sort would be required. But, since the code supplied to us by the OP only uses one sort, the stability of quick sort is irrelevant.

 

[Mute]

This seems wrong. The rest of the post seems to indicate there would always be 4 columns. To use qsort you should declare the array thusly:

double array[arraysize][4]

Yes, you're right. That was probably the issue, then. I looked up the order before I coded, but I must have confused myself and put it in wrong. Thanks for catching that.

One potential problem I was able to spot with comparefun2 is there is an assumption that a comparison that evaluates to true would evaluate to a specific positive integer. But AFAIK, such a compairson might evaluate to any non-zero integer.

I found that example somewhere online, so I'm not sure why it's like that, unless qsort doesn't really care if the values returned by the compare function are 0, +/- 1 or just 0 and postive or negative.