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!

What is output? Show the part of the code calling the fucntion — this
– this, Commented Apr 1, 2014 at 17:48
What is outputLength? Where is the definition of output? — SzG
– SzG, Commented Apr 1, 2014 at 17:51
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
– Deduplicator, Commented Apr 1, 2014 at 17:54
@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
– Deduplicator, Commented Apr 1, 2014 at 18:21

this · Accepted Answer · 2014-04-01 17:55:47Z

3

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

answered Apr 1, 2014 at 17:55

this

5,3031 gold badge25 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

21 Comments

Deduplicator Over a year ago

The address of the array is the address of the first element of the array, so no harm done!

Pete Over a year ago

@Deduplicator &output is the address of the pointer, not the address of the array.

Deduplicator Over a year ago

char array[2];assert((void*)array == (void*)&array);

this Over a year ago

@Deduplicator Show me where the standard guarantees that the address of the array is the same as the array? The next time it isn't the code will break. Such assumptions like yours cause the code to break years later.

alk Over a year ago

Assume char * p = malloc(10); then &p != p is true. @Deduplicator

|

Adrian McCarthy · Accepted Answer · 2014-04-01 18:07:34Z

1

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

answered Apr 1, 2014 at 18:07

Adrian McCarthy

49.8k16 gold badges136 silver badges194 bronze badges

3 Comments

macourtney7 Over a year ago

For what I'm doing I create an array from a hash table. So the length of the array is the same as the amount structs in the hash table that aren't still set as empty. I've made the changes you've suggested an still getting a segmentation fault.

Adrian McCarthy Over a year ago

Then I suspect the bug is in how you initialize the array from the hash table. It's probably time to learn how to use a debugger. ericlippert.com/2014/03/05/how-to-debug-small-programs

macourtney7 Over a year ago

Was nothing to do with the array. Was conditions external to the method causing issue. Thanks anyway.

ajay · Accepted Answer · 2014-04-01 18:44:26Z

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

macourtney7 · Accepted Answer · 2014-04-01 18:42:01Z

0

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

answered Apr 1, 2014 at 18:42

macourtney7

5412 gold badges10 silver badges25 bronze badges

2 Comments

chux Over a year ago

The correction of &output to output was only discernible by OP as OP did not post the declaration of output.

Alan Corey Over a year ago

I like the subtraction simplification, instead of a bunch of compares. Return the difference of dereferenced p and q. In my case I just came up with: return ((struct filerec *)p)->fsize - ((struct filerec *)q)->fsize; But it didn't work until I added the parens around (struct filerec *)q and p.

Collectives™ on Stack Overflow

Sorting structure with C qsort()

4 Answers 4

21 Comments

3 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

21 Comments

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related