Qsort and issues with it

Question

The following is my code and Qsort produces strange result:

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

char values[] = { 0x02,0x04,0x0b,0x16,0x24,0x30,0x48,0x6c};

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

int main ()
{

    int i;

    qsort (values, 8, sizeof(char), compare);

    for (i = 0; i < 8; i++)
    {
       printf ("%0x ",values[ i ]);
    }
    return 0;
}

The output of this is program is:

2 6c 48 30 24 4 b 16

Though it should have been the same as the input. Can someone please explain the reason why it is so and how I can correct it?

Answer 1

return ( *(int*)a - *(int*)b );

You should not be comparing int values if the underlying "objects" are char values.

What's almost certainly happening is that the comparison is using the four (depending on sizeof(int)) bytes to do the comparison, such as the first object being 0x02040b16 (depending on your endian-ness of course). This will greatly stuff up the process.

Change it to:

return ( *(char*)a - *(char*)b );

and try again.

And just be aware that the signed-ness of char is an implementation issue. You may find that 0x80 ends up being less than 0x7f. If that's not what you want, use unsigned char explicitly to extract the values, then upgrade them to signed integers (with another cast) before doing the subtraction.

In fact, for portability, you may want to use signed char explicitly for the other case as well.

The following program shows how it works with the correct underlying data type:

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

signed char values[] = {0x02, 0x04, 0x0b, 0x16, 0x24, 0x30, 0x6c, 0x48};

int compare (const void *a, const void *b) {
    return *(signed char*)a - *(signed char*)b;
}

int main (void) {
    int i;

    qsort (values, 8, sizeof (char), compare); // char okay here.
    for (i = 0; i < 8; i++)
       printf ("%0x ", values[i]);
    putchar ('\n');

    return 0;
}

The ouput of this is:

2 4 b 16 24 30 48 6c

(I swapped the order of the final two elements in the code so as to show it was actually sorting something).