Quickie: Qsort Compare Func Trick

May 25th, 2009 by Scott

Sitting at a bus stop in Lima, compiler running in the background, got a few minutes to kill. Quickie time!

I came across this trick for qsort in some code at work that August wrote. Cool trick, simple, can’t believe I haven’t seen this before. It’s probably in K&R and a million FAQ’s and so on, but I missed it anyway. In a Google for “qsort compare function sample” you get a mix of both tricks that come up.

Here’s a basic qsort compare proc that I pulled from one of the samples I found:

int sortFunction(const void *a, const void *b) { int intOne = *((int*)a); int intTwo = *((int*)b); if (intOne < intTwo) return -1; if (intOne == intTwo) return 0; return 1; }

Pretty straightforward, but here’s a smaller and quicker version!

int sortFunction(const void *a, const void *b) { int intOne = *((int*)a); int intTwo = *((int*)b); return intOne - intTwo; }

No branching is required. This is much faster as well as being shorter. This is great when you are sorting by multiple keys at once – you only need to test for 0 before moving on to the next sub-key, otherwise return the difference you already have.

Some important notes:

This obviously doesn’t work on non-numeric types like a string. Still have to do those the old way.
In C++ if you are using the std library you should use std::sort, which only requires a single < compare (unlike qsort’s troika of <0, 0, or >0 returns). Does not use callbacks, and inlines your comparison proc. Much faster than qsort.
If you do use this trick put a comment in the code mentioning it’s on purpose! At first it will look like a bug to a casual observer.

UPDATE: (10/10/2009)

Commenter Arseny points out that this can be dangerous! Put a big comment on the sort function noting that the caller needs to keep in mind the range of data being used.

It’s a good idea to put in a simple assert that tests for this.

I’d still not shy away from the technique. The boundary conditions are very far out, and unlikely for most scenarios. An assert would put my mind at ease.

Posted in c++, optimizing, trick |