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?

Answer 1

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.

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);
}

Answer 3

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

Answer 4

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!