0
votes

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!

4
What is output? Show the part of the code calling the fucntion - this
Full method containing qsort: pastebin.com/y6ziACWy - macourtney7
What is outputLength? Where is the definition of output? - SzG
Dont't do any explicit cast unless you both know what it does and it is really needed. Let the compiler warn you, no muzzling it. Also, always compile with -Wall -Wextra -pedantic - Deduplicator
@Matt: Please do not use any external code. Instead, give a MCVE. That is better all around. Especially when you hide that link in the comments. - Deduplicator

4 Answers

3
votes

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
1
votes

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;
}
1
votes

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);
0
votes

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