I came across a qsort comparator function that was incorrectly using "a > b" as the comparison operation. I would expect this code to just somewhat randomly reorder the array, but it was working on my school's instructional servers (Ubuntu 12.04.4 LTS). It didn't work on my own laptop as expected, so I'm not sure what could be causing this bug.
#include <cstdio>
#include <cstdlib>
void print_arr(int* arr, size_t n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int int_compar(const void *x, const void *y)
{
int i_x = *((int*)x);
int i_y = *((int*)y);
return i_x > i_y;
}
int main(int argc, char *argv[])
{
int n = (1<<4);
int in[n];
for(int i = 0; i < n; i++)
in[i] = rand() % 100;
printf("Before: ");
print_arr(in, n);
qsort(in, n, sizeof(int), int_compar);
printf("After: ");
print_arr(in, n);
return 0;
}
My laptop:
$ ./qsort_test
Before: 7 49 73 58 30 72 44 78 23 9 40 65 92 42 87 3
After: 23 7 9 3 58 44 42 40 49 30 65 72 73 78 87 92
Ubuntu:
$ ./qsort_test
Before: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26
After: 15 21 26 27 35 49 59 62 63 77 83 86 86 90 92 93
You are breaking the contract for using qsort
, thus invoking Undefined Behavior.
Specifically, your comparison-function is bad:
7.22.5.2 The qsort function
Synopsis
#include <stdlib.h> void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
Description
2 Theqsort
function sorts an array ofnmemb
objects, the initial element of which is pointed to bybase
. The size of each object is specified bysize
.
3 The contents of the array are sorted into ascending order according to a comparison function pointed to bycompar
, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.
4 If two elements compare as equal, their order in the resulting sorted array is unspecified.
Returns
5 Theqsort
function returns no value.
It should be more along the lines of:
int int_compar(const void *x, const void *y)
{
int i_x = *(int*)x;
int i_y = *(int*)y;
return i_x > i_y - i_x < i_y;
}
Now, the comparison-function is partially functional instead of completely broken, it does indicate whether the first is bigger than the second, but does not differentiate between them being equal or the second being bigger.
Depending on how the algorithm happens to be written, that might make the algorithm see all as equal, not react to your error at all, or do something funny.
For an example, all C++ standard-library sorting algorithms are written to only use less-than for comparison.