Sorting array of structs in C using qsort

Question

Let's define a struct named "Edge".

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

struct Edge{
    int first;
    int second;
    float score;
};

struct Edge* newEdge(int first, int second, float score){
    struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge*));
    edge->first = first;
    edge->second = second;
    edge->score = score;
    return edge;
}

Given an array of edges, each of which consists of two vertices and a score, I have to sort the edges in descending/ascending order of their scores. I've written a comparator function. The following is what I've tried. However, it doesn't produce the correct output.

int comparator_function(const void *v1, const void *v2){
    struct Edge* e1 = (struct Edge*) v1;
    struct Edge* e2 = (struct Edge*) v2;
    if(e1->score < e2->score){
        return 1;
    }
    return 0;
}

int main(){
    struct Edge* edges[5];
    edges[0] = newEdge(1, 2, 1.23);
    edges[1] = newEdge(4, 3, 3.222);
    edges[2] = newEdge(2, 2, 5.222);
    edges[3] = newEdge(5, 1, 4.222);
    edges[4] = newEdge(3, 4, 2.4);
    for(int i=0;i<5;i++){
        printf("%d, %d, %f\n", edges[i]->first, edges[i]->second, edges[i]->score);
    }
    printf("\n\n");

    qsort(edges, 5, sizeof(struct Edge*), comparator_function);

    for(int i=0;i<5;i++){
        printf("%d, %d, %f\n", edges[i]->first, edges[i]->second, edges[i]->score);
    }
    return 0;
}

The output of the quicksort I'm getting is -

4, 3, 3.222000
5, 1, 4.222000
2, 2, 5.222000
1, 2, 1.230000
3, 4, 2.400000

I'm not sure if my compare function is right or not. Any help would be appreciated.

MikeCAT · Accepted Answer · 2021-04-22 11:51:12Z

4

Firstly, the allocation

    struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge*));

is wrong. You have to allocate for the structure, not the pointer.

It should be

    struct Edge* edge = malloc(sizeof(*edge));

or

    struct Edge* edge = malloc(sizeof(struct Edge));

(Also note that casting results of malloc() is considered as a bad practice)

Then, the comparision function is wrong.

You have to return -1 when the first element is "smaller" than the second element.
The arguments are pointers to the elements (struct Edge* in this case).

It should be like this:

int comparator_function(const void *v1, const void *v2){
    /* correct casting type and add dereferencing */
    struct Edge* e1 = *(struct Edge**) v1;
    struct Edge* e2 = *(struct Edge**) v2;
    if(e1->score < e2->score){
        return 1;
    }
    /* add this */
    if(e1->score > e2->score){
        return -1;
    }
    return 0;
}

answered Apr 22, 2021 at 11:51

MikeCAT

75.1k11 gold badges50 silver badges71 bronze badges

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

2 Comments

Saankhya Mondal Over a year ago

Thank you for the quick response. The qsort function is now working properly. However, if I don't cast struct Edge* before malloc, it's showing the error that "invalid conversion from 'void*' to 'Edge*''. Is there a way to allocate memory without casting?

MikeCAT Over a year ago

It looks like you are compiling your code as C++. Use C compiler to compile C code. The extension of C source file should be .c.

dbush · Accepted Answer · 2021-04-22 12:00:36Z

1

The comparison function passed to qsort is supposed to return:

less than 0, if the value on the left is smaller
0, if the values are equal
greater than 0, if the value on the left is larger

Your comparison function only returns the values 0 and 1, so there's no way for the left argument to be larger. You need to add an extra case to account for that.

The other problem is that since your array element types are struct Edge *, the pointers passed to the comparison function will be of type struct Edge ** so you need to make a change related to that.

int comparator_function(const void *v1, const void *v2){
    struct Edge * const *e1 = v1;
    struct Edge * const *e2 = v2;
    if((*e1)->score < (*e2)->score){
        return 1;
    } else if((*e1)->score > (*e2)->score){
        return -1;
    } else {
        return 0;
    }
}

Also, you're not allocating the proper amount of memory:

struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge*));

This only allocates space for a pointer, not the entire struct. You want:

struct Edge* edge = malloc(sizeof(struct Edge));

edited Apr 22, 2021 at 12:00

answered Apr 22, 2021 at 11:52

dbush

233k27 gold badges261 silver badges334 bronze badges

4 Comments

MikeCAT Over a year ago

The array is struct Edge* edges[5];, so the 3rd argument of qsort() should be sizeof(struct Edge*) or sizeof(*edges), not sizeof(struct Edge).

dbush Over a year ago

@MikeCAT Fixed, and found some other issues.

Saankhya Mondal Over a year ago

@dbush, Thank you for the quick response. The qsort function is now working properly. However, if I don't cast struct Edge* before malloc, it's showing the error that "invalid conversion from 'void*' to 'Edge*''. Is there a way to allocate memory without casting?

dbush Over a year ago

@SaankhyaMondal C allows casting to/from a void * without a cast. If you're getting that error that means you're compiling with a C++ compiler. Use a C compiler instead.

Collectives™ on Stack Overflow

Sorting array of structs in C using qsort

2 Answers 2

2 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related