14 
#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

Improve this question
1
  • 2
    qsort works fine. Your call to qsort is broken. Commented Oct 7, 2010 at 23:19

3 Answers 3

Reset to default
44

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

+1 There needs to be more plus ones and this needs to be accepted as the answer.
return (fa > fb) - (fa < fb) is elegant, yet return (fa < fb) ? -1 : (fa > fb); may be faster. YMMV.
In many embedded and other environments, FP operations are performance expensive. The (fa < fb) ? -1 : (fa > fb) approach performs 1 or 2 FP compares and (fa > fb) - (fa < fb) always performs 2. Given random order: 1.5 compares is faster than 2 on an operation that may dominate qsort(). Optimization, etc. may affect how well the each approach works. A good compiler may be able to only do 1 compare either way, identifying it can re-use the compare results. But doubtful (fa < fb) ? -1 : (fa > fb) would ever be slower.
@chux: Only a low quality compiler would perform two comparisons when doing (fa > fb) - (fa < fb). Most CPUs compare values by using a CPU instruction that sets certain CPU state flags. These state flags fully describe the result of the comparison. A single fa vs. fb comparison generates the flags that cover all relational comparisons between fa and fb. I.e. one comparison immediately gives you the answer to both fa > fb and fa < fb. All that is needed is to extract these results from the CPU flags and perform the subtraction.
@chux: Your (fa < fb) ? -1 : (fa > fb) is potentially branching. The fact that it is branching suggests that it might end up being much slower.
|
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.

Improve this answer

3 Comments

Will not work. This function will return -1 for equal values, meaning that for equal a and b comparing a to b will say that a < b, yet comparing b to a will say that b < a. qsort will not work correctly with such comparison function.
Yor edit didn't change anything, except that now equal values will always return 1. Standard qsort is designed for a comparator that is a tri-value function. It is not generally possible to reduce it to a two-value function, regardless of what you do. You have to return -1, 0, +1.
It is not unusual for a debug implementation of qsort to check the correctness of the comparison function. If your comparison function will return 1 for (a, b) comparison and at the same time return 1 for (b, a) comparison, such debug qsort implementation will typically abort immediately with an asserion failure. The non-debug implementation will simply produce undefined behavior.
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.