Problem trying to use the C qsort function

问题:

#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

回答1:

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.

回答2:

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.

回答3:

To add to existing answer by @AnT, you can automatically verify your qsort callback via SortChecker:

$ LD_PRELOAD=$HOME/sortcheck-master/bin/libsortcheck.so ./a.out
a.out[7133]: qsort: comparison function is not transitive (comparison function 0x4005cd (/home/iuriig/a.out+0x4005cd), called from 0x400614 (/home/iuriig/a.out+0x400614), cmdline is "./a.out")
-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

This warning says that compare reports x < y, y < z and not x < z for some inputs. To further debug this issue, run with

export SORTCHECK_OPTIONS=raise=1

and examine generated codedump.