Qsort Comparison Function

I don't understand why you need all the extra things in the compare function so I simplified it to this

Whether you use const qualifier is up to you. You are expected to not modify the values in the comparator. But it's possible to cast away the const and break the promise you make to the compiler.


qsort expects a function pointer which takes two const void * as parameters which is why pointers are passed for the comparator function:

   void qsort(void *base, size_t nmemb, size_t size,
                  int(*compare)(const void *, const void *));

So passing a and b would lead to interpreting the values as pointers which is obviously wrong.


It works without passing pointers for multi-dimensional arrays because when you pass arrays, they decay into pointers. So the following comparator you have is ok.

int compare (int a[2], int b[2])
{
    return a[1] - b[1];
}

This still works, and produces the same results. Can anyone explain to me what I removed, and why it still works?

You are invoking undefined behavior in C. See C99 6.3.2.3 Pointers/8:

A pointer to a function of one type may be converted to a pointer to a function of another type and back again; the result shall compare equal to the original pointer. If a converted pointer is used to call a function whose type is not compatible with the pointed-to type, the behavior is undefined.

In C++, this program is flat-out ill-formed: http://ideone.com/9zRYSj

It still "happens to work" because the compare function expects a pair of pointers; and on your particular platform sizeof(void*) is the same as sizeof(int*), so calling a function pointer of type int(void *, void *) which in fact contains a pointer to a function of type int(int *, int *) is effectively the same as the pointer type casts on your particular platform at this particular point in time.

Additionally, do I really need to use pointers? Why can't I just compare "a" and "b" directly like so (this does NOT work):

Because qsort takes a general comparison function for any two types; not just int. So it doesn't know what type to which the pointer is dereferenced.

For some reason, with a multidimensional array, I was able to get away with NOT using pointers and for some reason it worked! what is going on!

This is because the following prototypes are the same:

  1. int foo(int *a, int *b);
  2. int foo(int a[], int b[])

That is, an array decays into a pointer when passed to a function. Explicitly specifying the length of the array as you did:

int foo(int a[2], int b[2])

causes the compiler to make sizeof and other compile time bits to treat the item as a two element array; but the function still accepts a pair of pointers when it gets down to the machine level.

In any of these cases, passing a comparison function that does not take a pair of void *s results in undefined behavior. One valid result of "undefined behavior" is "it just seems to work". Another valid result would be "it works on Tuesdays" or "it formats the hard disk". Don't rely on this behavior.