c - Qsort Comparison Function

Question

I am a beginner to C and I am trying to understand the comparison function needed for the qsort function.

Part One: Syntax

A simple suggested use is this (I have included some main() code to print the results as well):

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

int values[] = { 40, 10, 100, 90, 20, 25, 12, 13, 10, 40 };

int compare(const void *a, const void *b)
{
    const int *ia = (const int *)a; // casting pointer types 
    const int *ib = (const int *)b;
    return *ia  - *ib; 
}

int main()
{
    int n;
    for (n=0; n<10; n++)
    {
        printf("%d ",values[n]);
    }
    printf("
");
    qsort(values, 10, sizeof(int), compare);
    for (n=0; n<10; n++)
    {
        printf("%d ",values[n]);
    }
    printf("
");
    system("pause");
    return 0;
}

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

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

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

Part Two: Why Pointers?

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

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

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? (Example code of sorting a multidimensional array by the 2nd item in each sub array):

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

int values[7][3] = { {40,55}, {10,52}, {100,8}, {90,90}, {20,91}, {25,24} };

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

int main()
{
    int n;
    for (n=0; n<6; n++)
    {
        printf("%d,",values[n][0]);
        printf("%d ",values[n][1]);
    }
    printf("
");
    qsort(values, 6, sizeof(int)*3, compare);
    for (n=0; n<6; n++)
    {
        printf("%d,",values[n][0]);
        printf("%d ",values[n][1]);
    }
    printf("
");
    system("pause");
    return 0;
}

I am really glad the multidimensional array sorting is working as that is my end goal anyway, but I have no idea how I managed to get it to work (other than dumb luck and chopping up the code) so I would really love some explanation as to why some of the examples I provided work, and why some don't!

Answer 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.