How to qsort an array of struct

Question

So I was tasked with grabbing a binary file, reading it into an array composed of structs then sorting it based on an array within the struct. The part that I'm stuck on is the sorting. I'm not sure if I'm supposed to sort it as an array (since the binary file is now an array) or sort it as a struct. Heres part of my code bellow.

typedef struct {
    char FlightNumber[7];
    char OriginCode [5];
    char DestinationCode [5];
    int Date [];
} FLIGHT;

int main(){

FLIGHT FlightData [3000];
/*opens file, freads it into the array then closes*/

/*trying to sort it based on OriginCode*/
int compare (const FLIGHT *a, const FLIGHT *b) {
    FLIGHT *ia = (FLIGHT *)a;
    FLIGHT *ib = (FLIGHT *)b;

    return strcmp(ia->OriginCode, ib->OriginCode);}

qsort( FlightData, 3000, sizeof( FLIGHT ), compare);
/*to see if sorting worked...*/
for (i = 0; i < 100; i++){

    printf ("%i) %s, %s, %s\n", i, FlightData[i].FlightNumber, FlightData[i].OriginCode, FlightData[i].DestinationCode );
}
}

Basically I'm lost on how to write the compare.

Similar question: http://stackoverflow.com/questions/6105513/need-help-using-qsort-with-an-array-of-structs — Ilya, Apr 14 '14 at 04:33
possible duplicate of [How to sort an array of structs in C?](http://stackoverflow.com/questions/8721189/how-to-sort-an-array-of-structs-in-c) — Jonathan Leffler, Apr 14 '14 at 04:46

score 2 · Answer 1 · answered Apr 14 '14 at 04:35

Note that Date has zero-size here because you do not allocate any space for it. It would be undefined behaviour to dereference it.

The qsort comparison function has to have this type:

int compare(const void *a, const void *b)

Your comparator should work so long as you change your function signature to match this.

Jonathan Leffler · Accepted Answer · 2014-04-14T04:46:12.433

First off, the comparator function should have the signature:

int compare(const void *v1, const void *v2);

Next, you convert the void pointers into your structure pointers:

    const FLIGHT *ia = (FLIGHT *)v1;
    const FLIGHT *ib = (FLIGHT *)v2;

Next, you need to compare things systematically, element by element:

    int rc;

    if ((rc = strcmp(ia->OriginCode, ib->OriginCode)) != 0)
        return rc;
    if ((rc = strcmp(ia->DestinationCode, ib->DestinationCode)) != 0)
        return rc;
    …
    return 0;  // Only if the two entries compare as identical

This sorts by origin airport code, destination airport code, then by other criteria you can decide (flight number, date). I note that you've not specified how the date is stored. Since it is an integer array (apparently a 'flexible array member'), you probably have 'year, month, day' separately in some sequence.

When you have a flexible array member, you should not define an array of the structure, because you cannot store anything in the flexible array member. You can have an array of pointers, but you need to allocate the structures separately. OTOH, you really don't need variable size arrays to describe a date. You should be using a fixed size array, or even a timestamp to give time and date. The residual problem is with flights that depart on one day and arrive on another — overnighters and flights across the international date line. You probably need a departure time and an arrival time, in practice.

See also (amongst many others, no doubt):

I was wondering this, which made me not look at most help I found, but would the comparator for a char and an int (both array or not) be written the same? — Yitzak Hernandez, Apr 14 '14 at 04:53
It depends on what you mean. If you were sorting an array of `int`, then you'd probably use `int i1 = *(int *)v1; int i2 = *(int *)v2; if (i1 < i2) return -1; else if (i1 > i2) return +1; else return 0;` for the function body. The point of those comparisons is to avoid arithmetic overflow (people often write `return i1 - i2;` but if there's a chance of arithmetic overflow, all hell breaks loose). See 'How to sort an array of structs' for more information on this. — Jonathan Leffler, Apr 14 '14 at 05:01
Also, for integers, you can use the comparison `return (i1 > i2) - (i1 < i2);` If `i1 > i2`, this returns +1; if `i1 < i2`, it returns -1; otherwise, it returns 0. It might manage to avoid conditionals, which can make a difference in a pipelined architecture. It also always performs two comparisons, so it has uniform timing. — Jonathan Leffler, Apr 14 '14 at 05:10

How to qsort an array of struct

2 Answers2