Problem trying to use the C qsort function

Question

#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

Answer 1

By rounding the difference to the integer you lose the precision.

EDIT:

Modify the compare function to

return (*(float*)a >= *(float*)b) ? 1 : -1;

Edit for AndreyT: I don't think that returning only 1 or -1 will cause an infinite loop or incorrect ordering (it will just exchange equal values that didn't require it).

Having an explicit case for returning 0 will cost an additional float compatation, and they are rarely equal. So, the comparation for equallity could be omitted if the collision rate in the input data is small.

Answer 2

Your comparison function is broken. It says, for example, that -1 is equal to -1.1. In other words, you yourself told qsort that the relative order of -1 and -1.1 does not matter. Why are you surprised that in the result these numbers 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, as you observed yourself. For integer types it overflows.

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 = *(float*) a;
  float fb = *(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 the comparisons out explicitly.