CODEWITHSUNDEEP
cqsort
twfx
twfx

Reputation: 1694

qsort for structure array

I try to sort a struct below, given an intention to sort their error rate, while retaining the information of sid and did. While there is no compilation error, I get a seg fault in runtime. I wonder what has gone wrong....

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

struct linkdata {
    int sid;
    int did;
    double err;
};
typedef struct linkdata LD;
typedef int (*qsort_func_t)(const void *, const void *);

static int compareByErr (const void * a, const void * b)
{
    fprintf(stderr, "aerr=%.3f, berr=%.3f\n", (*(LD**)a)->err, (*(LD**)b)->err);
    int aerr = (*(LD**)a)->err;
    int berr = (*(LD**)b)->err;

    return aerr - berr;
}

int main() {

    int idx;
    int numnode;
    struct linkdata* perr;
    qsort_func_t qsort_func = compareByErr;

    numnode = 3;
    perr = (LD*) malloc (numnode*numnode*sizeof(LD));

    perr[0].sid = 0; perr[0].did = 1; perr[0].err = 0.642; 
    perr[1].sid = 0; perr[1].did = 2; perr[1].err = 0.236; 
    perr[2].sid = 0; perr[2].did = 3; perr[2].err = 0.946;
    idx = 3;

    qsort(perr, idx, sizeof(perr), compareByErr);

    int i;
    for (i=0; i<idx; i++){
       fprintf(stderr,"err[%d][%d] = %.3f\n", perr[i].sid, perr[i].did, perr[i].err);            
    }

    free(perr); 
}

Upvotes: 2

Views: 1965

Answers (3)

kennytm
kennytm

Reputation: 523304

There are many errors in the code.

1. compareByErr

The a and b parameters of the compareByErr function are objects of LD*, not LD**. You did an unnecessary dereferencing. Try to change that function to:

static int compareByErr (const void * a, const void * b)
{
    fprintf(stderr, "aerr=%.3f, berr=%.3f\n", ((LD*)a)->err, ((LD*)b)->err);
    int aerr = ((LD*)a)->err;
    int berr = ((LD*)b)->err;

    return aerr - berr;
}

2. compareByErr

There is another problem, that you implicitly convert the double into int. Since all those "errors" are 0.???, they will all be truncated to 0. Making the whole array unsorted. Change it to:

    double aerr = ((LD*)a)->err;
    double berr = ((LD*)b)->err;

    return aerr < berr ? -1 : aerr > berr ? 1 : 0;

3. malloc

You are allocating for 32 nodes, but only 3 are needed. Change that to 

perr = (LD*) malloc (numnode * sizeof(LD));

4. qsort

The 3rd argument is the size of each element of the array, not sizeof(perr) which is just the size of a pointer (4 bytes). Change that line to:

qsort(perr, idx, sizeof(*perr), compareByErr);
//                      ^

to actually get the element size.

The idx seems unnecessary. You could just use numnode here.

Upvotes: 2

Alan Curry
Alan Curry

Reputation: 14711

Your comparison function expects to be sorting an array of pointers to structs, but you're not doing that. This problem is covered by the other answers.

What they didn't mention is that you're also using the wrong sizeof for the sort. Since the array is an array of structs, you must tell qsort that the size of a member is the size of a struct. Change sizeof perr to sizeof *perr

Also, converting the floats to ints before comparing them results in them all being equal because they're all zero...

Upvotes: 2

unwind
unwind

Reputation: 399843

You're mis-treating the arguments to your comparator callback.

This:

fprintf(stderr, "aerr=%.3f, berr=%.3f\n", (*(LD**)a)->err, (*(LD**)b)->err);

should be:

{
  const LD *lda = a, *ldb = b;

  fprintf(stderr, "aerr=%.3f, berr=%.3f\n", lda->err, ldb->err);
  /* ... */
}

Of course you don't have to introduce new variables of the proper type, but it makes the subsequent code that much easier. I always do this.

Further, this:

int aerr = (*(LD**)a)->err;
int berr = (*(LD**)b)->err;

return aerr - berr;

is adoringly terse, but it can hide integer overflow issues that are bit scary. I would recommend:

return (a->err < b->err) ? -1 : a->err > b->err;

This uses an explicit literal to generate the -1 value, while relying on comparisons generating 0 or 1 for the two other cases.

Upvotes: 1

Related Questions