Sorting structure with C qsort()

Question

Having trouble getting my head around implementing the qsort() built into C to sort an array of structs by a stored int value (hitCount).

My struct:

typedef struct words {
    const char *word;
    int hitCount;
} words;

I'm trying to use the example given by Microsoft (http://support.microsoft.com/kb/73853).

So I've got at the top:

typedef int (*compfn)(const void*, const void*);

and the comparision method:

int compare (words *a, words *b) {
    if (a->hitCount > b->hitCount) {
        return -1;
    } else if (a->hitCount < b->hitCount) {
        return 1;
    } else {
        return 0;
    }
}

then within another method I call qsort with my array name and other details replacing the Microsoft example:

qsort((void *) &output, outputLength, sizeof(words), (compfn)compare);

This gives a segmentation fault.

I don't fully understand how to use qsort so I assume where I've adapted it from Microsoft's example I've done it incorrectly.

I hope I've included the mistake and can get some enlightenment as to what I should be doing in order for this to work correctly.

Many Thanks!

Answer 1

You have to pass the array not the address of the array to qsort.

qsort( output, ... );

Also your compare function must return an int and accept two const void* arguments. Casting your function int compare (words *a, words *b) to a different( yet correct ) type which is then called by qsort() will cause undefined behaviour.

The compare function must be:

int compare (const void *a, const void *b)...

Then you cast a and b to correct types:

((words*)a)->hitCount < ((words*)b)->hitCount

Answer 2

I suspect that outputLength is computed incorrectly. A complete working example:

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

typedef struct words {
    const char *word;
    int hitCount;
} words;

int compare(const void * left, const void * right) {
    const words * a = (const words *) left;
    const words * b = (const words *) right;
    if (a->hitCount > b->hitCount) {
        return -1;
    } else if (a->hitCount < b->hitCount) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    struct words output[] = {
      { "hello", 314 },
      { "world", 42 },
      { "answer", 42 }
    };
    int outputLength = sizeof(output) / sizeof(output[0]);
    int i;

    output[0].word = "hello";
    output[0].hitCount = 314;
    output[1].word = "world";
    output[1].hitCount = 42;
    qsort(output, outputLength, sizeof(words), compare);

    for (i = 0; i < outputLength; ++i) {
        printf("%d %s\n", output[i].hitCount, output[i].word);
    }

    return 0;
}

Answer 3

The prototype of the standard library function qsort is

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

Note the signature of the compare function. You cannot typecast a pointer to a function of different signature and make it work correctly. Therefore, typecasting your compare function will not work. It must have the same signature as declared in the prototype of qsort. Change your compare function to -

int compare(const void *a, const void *b) {
    int c = ((words *) a)->hitCount;
    int d = ((words *) b)->hitCount;

    if(c > d) return -1;
    if(c < d) return 1;
    return 0;
}

The first argument base of qsort is the base address of the buffer which contains the elements to be sorted. Also, any pointer type is assignment compatible to a void * variable and as such you don't need to cast the base address. Therefore, you should call the qsort function as -

qsort(output, outputLength, sizeof output[0], compare);

Answer 4

Got it working with:

    int compare (const void *a, const void *b) {
        if (((words *)a)->hitCount > ((words *)b)->hitCount) {
            return -1;
        } else if (((words *)a)->hitCount < ((words *)b)->hitCount) {
            return 1;
        } else {
            return 0;
        }
    }

and call to sort:

    qsort(output, outputLength, sizeof(words), compare);

Thanks to everyone's help but majority credit to "self".