#include <stdio.h>
#include <stdlib.h>
float values[] = { 4, 1, 10, 9, 2, 5, -1, -9, -2,10000,-0.05,-3,-1.1 };
int compare (const void * a, const void * b)
{
return ( (int) (*(float*)a - *(float*)b) );
}
int main ()
{
int i;
qsort (values, 13, sizeof(float), compare);
for (i = 0; i < 13; i++)
{
printf ("%f ",values[ i ]);
}
putchar('\n');
return 0;
}
The result is:
-9.000000 -3.000000 -2.000000 -1.000000 -1.100000 -0.050000 1.000000 2.000000 4.000000 5.000000 9.000000 10.000000 10000.000000
It's wrong because the order of -1 and -1.1 is changed. I believe it is happening because my "compare" function.
How can I fix this?
Thanks
The qsort() function sorts an array of num elements, each of width bytes in size, where the first element of the array is pointed to by base. The compare pointer points to a function, which you supply, that compares two array elements and returns an integer value specifying their relationship.
The qsort() is a C library function that uses a quick sort algorithm to sort an array. Here is how it is declared in C: A void pointer is a pointer that can point to any datatype. The most interesting part of the syntax above is the comparator function. It is called by qsort() , multiple times, to compare two elements.
Since quicksort is an unstable sort — there are multiple possible results when the array contains equivalent elements — this means qsort() is not guaranteed to be stable, even if internally the C library is using a stable sort like merge sort. The C standard library has no stable sort function.
As the name suggests, qsort function uses QuickSort algorithm to sort the given array, although the C standard does not require it to implement quicksort.
Your comparison function is broken. It says, for example, that -1.0
is equal (equivalent) to -1.1
, since (int) ((-1.0) - (-1.1))
is zero. In other words, you yourself told qsort
that the relative order of -1.0
and -1.1
does not matter. Why are you surprised that in the resultant ordering these values are not sorted?
In general, you should avoid comparing numerical values by subtracting one from another. It just doesn't work. For floating-point types it might produce imprecise results for quite a few different reasons, one of which you just observed yourself. For integer types it might overflow.
The generic idiom for comparing two numerical values a
and b
for qsort
looks as (a > b) - (a < b)
. Remember it and use it. In your case that would be
int compare (const void * a, const void * b)
{
float fa = *(const float*) a;
float fb = *(const float*) b;
return (fa > fb) - (fa < fb);
}
In C code it might make perfect sense to define a macro
#define COMPARE(a, b) (((a) > (b)) - ((a) < (b)))
and use it instead of spelling out the comparisons explicitly.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With