13

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?

Improve this question

4 Answers 4

Reset to default
48

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!

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

Comments

19

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); }
Improve this answer

5 Comments

Don't try this in another language with booleans, though. ;)
@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++.
@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.
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).
@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.
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.

Improve this answer

Comments

0

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
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.