How to sort struct using qsort

Question

I am trying to use qsort to sort a struct containing pointers. Is the problem with the comparison function? How do I fix so I can sort based on the cc.

Here is the code:

#include <stdlib.h>
#include <string.h>

typedef enum {
    PETROL,
    DIESEL,
    ELECTRIC,
    LPG,
    BIOFUEL,
    OTHER
} fuel_t;

typedef struct car_tag {
    unsigned cc;
    fuel_t fueltype;
} car_t;


typedef struct fleet_tag {
    car_t ** cars;
    size_t n_cars;
} fleet_t;

int car_comp(const void * vp1, const void * vp2) {
    const car_t* const c1 = vp1;
    const car_t* const c2 = vp2;
    if (c1->cc > c2->cc)
        return -1;
    else if (c1->cc < c2->cc)
        return 1;
    else {
        return 0;
    }
}


int main() {
    car_t array[] = {
        { 600, PETROL},
        {1200, PETROL},
        {1000, PETROL},
        {1600, DIESEL},
        {1000, ELECTRIC}
    };

    int size = sizeof(array) / sizeof(array[0]);

    fleet_t fl;
    fl.n_cars = size;
    fl.cars = malloc(size * sizeof(car_t));

    for (int i = 0; i < size; i++) {
        car_t* pc = malloc(sizeof(car_t));
        memcpy(pc, &array[i], sizeof(car_t));
        fl.cars[i] = pc;
    }

    // how to sort cars by cc
    qsort(&fl, fl.n_cars, sizeof(car_t), car_comp);

    // sort function doesn't correctly sort fleet of cars by cc
}

@MadPhysicist "How do I fix so I can sort based on the cc" – Angus Comber Jul 07 '18 at 16:03 — Angus Comber, Jul 07 '18 at 16:03

WhozCraig · Accepted Answer · 2018-07-07T16:28:16.107

I don't see the need for the dynamic allocation and memcpy invoke for each to-be-sorted car in this code at all.

You're building a pointer bed (a sequence of pointers) so why not just allocate that (which you're doing), and then store the addresses of each element from array there. Then, tailor your comparator to address what you're sending: an address of a pointer (pointer to pointer) and setup the dereferences accordingly

Add to that, you should be passing fl.cars to qsort, not &fl, and the sizeof argument therein is also wrong.

Finally, I don't know if you intentionally wanted to use a greater-than logic stack in your comparator, but that is exactly what you ended up with.

Example

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

typedef enum {
    PETROL,
    DIESEL,
    ELECTRIC,
    LPG,
    BIOFUEL,
    OTHER
} fuel_t;

typedef struct car_tag {
    unsigned cc;
    fuel_t fueltype;
} car_t;


typedef struct fleet_tag {
    car_t ** cars;
    size_t n_cars;
} fleet_t;

int car_comp(const void * vp1, const void * vp2)
{
    const car_t * const *pc1 = vp1;
    const car_t * const *pc2 = vp2;

    if ((*pc1)->cc > (*pc2)->cc)
        return -1;

    if ((*pc1)->cc < (*pc2)->cc)
        return 1;

    return 0;
}


int main() {
    car_t array[] = {
        { 600, PETROL},
        {1200, PETROL},
        {1000, PETROL},
        {1600, DIESEL},
        {1000, ELECTRIC}
    };

    int size = sizeof(array) / sizeof(array[0]);

    fleet_t fl;
    fl.n_cars = size;
    fl.cars = malloc(size * sizeof *fl.cars);

    for (int i = 0; i < size; i++)
        fl.cars[i] = array+i;

    // how to sort cars by cc
    qsort(fl.cars, fl.n_cars, sizeof *fl.cars, car_comp);

    for (int i=0; i<size; ++i)
        printf("%d (%u, %d)\n", i+1, fl.cars[i]->cc, fl.cars[i]->fueltype);

    free(fl.cars);

    return EXIT_SUCCESS;
}

Output

1 (1600, 1)
2 (1200, 0)
3 (1000, 0)
4 (1000, 2)
5 (600, 0)

qsort works by feeding it a sequence of "things", a length stating how many "things" there are, a size noting how big each "thing" in the sequence is, and finally a comparator function which will be fed the address of each "thing" during execution of the algorithm.

In your case, your "things" are pointers to car_t structures. In fact,

Your sequence is a dynamic array of pointers; your "thing" is a pointer to a car_t.
You length is size.
Your size of each "thing" is the size of a pointer.
Your comparator will access the address of two of your things (therefore, two pointers, so pointers to pointers), and act accordingly.

Therefore, the call becomes:

qsort(fl.cars, fl.n_cars, sizeof *fl.cars, car_comp);

Finally, note that the original array remains unchanged. The sort modified your pointer bed only. That was probably desirable, and I hope you understand how it works.

How to sort struct using qsort

1 Answers1

Linked