C qsort not working correctly

Question

I don't know what I'm doing wrong but the following code does not sort the array properly.

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

int main()
{
    int x[] = { -919238029,
            -889150029,
            -826670576,
            -579609061,
            -569653113,
            -305140505,
            -216823425,
            -193439331,
            -167683147,
            -49487019,
            -45223520,
            271789961,
            275570429,
            444855014,
            559132135,
            612312607,
            664554739,
            677860351,
            1005278191,
            1031629361,
            1089012280,
            1115952521,
            1521112993,
            1530518916,
            1907515865,
            1931470931,
            -1631034645,
            -1593702794,
            -1465300620,
            -1263094822
         };
    int i;

    qsort(x, 30, sizeof(int), compare);
    for(i = 0; i < 30; i ++)
        printf("%d\n", x[i]);

    return 0;
}

produces the following output:

1521112993
1530518916
1907515865
1931470931
-1631034645
-1593702794
-1465300620
-1263094822
-919238029
-889150029
-826670576
-579609061
-569653113
-305140505
-216823425
-193439331
-167683147
-49487019
-45223520
271789961
275570429
444855014
559132135
612312607
664554739
677860351
1005278191
1031629361
1089012280
1115952521

I mean, the problem /must/ be in my compare function. Anybody notice anything strange?

Trout

Answer 1

Yeah, your "comparison" overflows. :(

Reason:

When you subtract a negative number from a positive number, your result is not necessarily positive; if it can't be represented in the data type, it'll "wrap around" the other side.

Example:

If your integer can only hold from -8 to 7 (4 bits), then what happens when you compare 4 to -4?
Well, you get 8, which is 1000 in binary, which is -8. So 4 is less than -4.

Moral:

Don't do subtraction instead of comparison, even if they tell you "look how cool this is" at school!

Ethnocentrism

Answer 2

In general case you can't use subtraction to compare integers. Or, more precisely, you can, but only in situations when you are sure that the subtraction will not overflow. In your case subtraction overflows, producing totally meaningless results (not even mentioning that when signed integer subtraction overflows the behavior is undefined).

The common idiom for generating tri-state C-style comparisons between values a and b is the (a > b) - (a < b) expression. It works for data of virtually any comparable types. In your case the comparison function might look as follows

int compare(const void* a, const void* b)
{
  int va = *(const int*) a;
  int vb = *(const int*) b;
  return (va > vb) - (va < vb);
}

Streit

Don't try this in another language with booleans, though. ;) – Ethnocentrism

@Mehrdad: If you are referring to C++, you are wrong. This idiom works perfectly well in C++ as well. In C++ values of type bool are promoted to int before subtraction. Again, this idiom is perfectly safe with all fundamental types in C and C++. – Streit

@AndreyT: I was certainly not referring to C++ (mainly C# and Java). ;) C++ preserves a lot of the same behavior so it's obviously fine there. – Ethnocentrism

Common among whom? I much prefer the straightforward va < vb? -1 : va > vb? 1 : 0 which, is easy to understand, easy to invert, and easy to scale if you have multiple sort fields. And Mehrdad's comment is accurate -- there are many languages in which booleans are not implicitly converted to integers (of course, this is a C question, but then, he did grin). – Knowling

@Jim Balter: I find the (va > vb) - (va < vb) significantly more straightforward. It looks a bit novel at first, but its symmetrical nature quickly makes it more readable than a two-leveled convolution of ?: operators with non-obvious grouping. – Streit

Answer 3

To add to Mehrad's correct answer, here's an automated way to find bug in your code using SortChecker:

$ LD_PRELOAD=$HOME/sortcheck-master/bin/libsortcheck.so ./a.out
a.out[38699]: qsort: comparison function is not transitive (comparison function 0x40057d (/home/iuriig/a.out+0x40057d), called from 0x400693 (/home/iuriig/a.out+0x400693), cmdline is "./a.out")
-919238029
-889150029
...

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.

Gibran

Answer 4

I'm giving a code example using the information above. In my compiler and system, I get the same results as Ram who asked the question. This indicates that my integers are something like Ram's integers. I modified my code along the lines suggested by Mehrdad to use comparison operators instead of a subtraction. Then I got the numbers sorted properly.

Here is the code:

    #include <stdio.h>
    #include <stdlib.h>

    int compare(const void* a, const void* b)
    {
        int
            n1 = * (int *) a,
            n2 = * (int *) b;

        /*
        Usine the ternary to express along the lines of
            if
            elseif
            elseif
            .
            .
            .
            else
        */

        return 
            n1 > n2             // if
            ? 1                 // then
            : n1 == n2          // else if
            ? 0                 // then
            : -1                // else
            ;                   // end if
    }

    int main(int argc, char * argv[])
    {
        int x[] = 
        { 
            -919238029, -889150029, -826670576, -579609061, -569653113, -305140505, -216823425, -193439331,
            -167683147, -49487019,  -45223520,  271789961,  275570429,  444855014,  559132135,  612312607,
            664554739,  677860351,  1005278191, 1031629361, 1089012280, 1115952521, 1521112993, 1530518916,
            1907515865, 1931470931, -1631034645,-1593702794,-1465300620,-1263094822
        };

        int 
            i = 0,                          // index
            imax = sizeof(x)/sizeof(int);   // max value for index

        FILE * outf = 0;

        if ( !(outf = fopen("output.txt", "wt")) )
        {
            puts("outf == 0 which is an error trying to open \"output.txt\" for writing.\n");
            getch();
            return;
        }

        qsort(x, imax, sizeof(int), compare);


        for(i = 0; i < imax; i ++)
            fprintf(outf, "%d\n", x[i]);

        fclose(outf);

        return 0;
    }

And I get this output:

-1631034645
-1593702794
-1465300620
-1263094822
-919238029
-889150029
-826670576
-579609061
-569653113
-305140505
-216823425
-193439331
-167683147
-49487019
-45223520
271789961
275570429
444855014
559132135
612312607
664554739
677860351
1005278191
1031629361
1089012280
1115952521
1521112993
1530518916
1907515865
1931470931

Boyce