How to sort an array of structs in C?

Question

I have got an array of the following structs:

typedef struct _my_data_ 
{
  unsigned int id;
  double latitude;
  double longitude;
  unsigned int content_len;
  char* name_dyn;
  char* descr_dyn;
} mydata;

and I would like to sort it ascending by the ID field. I read it is possible to sort arrays using the qsort function but I am not sure how to correctly use it when sorting structs.

Solution

You need a structure comparator function that matches the prototype of the function expected by qsort(), viz:

int md_comparator(const void *v1, const void *v2)
{
    const mydata *p1 = (mydata *)v1;
    const mydata *p2 = (mydata *)v2;
    if (p1->id < p2->id)
        return -1;
    else if (p1->id > p2->id)
        return +1;
    else
        return 0;
}

If you ever get to a more complex sort criterion, this is still a good basis because you can add secondary criteria using the same skeleton:

int md_comparator(const void *v1, const void *v2)
{
    const mydata *p1 = (mydata *)v1;
    const mydata *p2 = (mydata *)v2;
    if (p1->latitude < p2->latitude)
        return -1;
    else if (p1->latitude > p2->latitude)
        return +1;
    else if (p1->longitude < p2->longitude)
        return -1;
    else if (p1->longitude > p2->longitude)
        return +1;
    else
        return 0;
}

Clearly, this repeats for as many criteria as you need. If you need to call a function (strcmp()?) to compare values, call it once but assign the return to a local variable and use that twice:

int md_comparator(const void *v1, const void *v2)
{
    const mydata *p1 = (mydata *)v1;
    const mydata *p2 = (mydata *)v2;
    int rc;
    if (p1->latitude < p2->latitude)
        return -1;
    else if (p1->latitude > p2->latitude)
        return +1;
    else if (p1->longitude < p2->longitude)
        return -1;
    else if (p1->longitude > p2->longitude)
        return +1;
    else if ((rc = strcmp(p1->name_dyn, p2->name_dyn)) < 0)
        return -1;
    else if (rc > 0)
        return +1;
    else
        return 0;
}

Also, this template works when data members are unsigned integers, and it avoids overflow problems when comparing signed integers. Note that the short cut you might sometimes see, namely variations on:

int md_comparator(const void *v1, const void *v2)   /* BAD */
{                                                   /* BAD */
    const mydata *p1 = (mydata *)v1;                /* BAD */
    const mydata *p2 = (mydata *)v2;                /* BAD */
    return(p1->id - p2->id);                        /* BAD */
}                                                   /* BAD */

is bad if id is unsigned (the difference of two unsigned integers is never negative), and subject to overflow if the integers are signed and of large magnitude and opposite signs.

Comments

[user703016]

Thank you for your comment and +1 by the way!

[beta]

Many thanks for your answer, I'm going to try this code right now.

[Jonathan Leffler]

Meditations on 'if id is unsigned': since the return is int, the unsigned value will be converted to int, so it could become negative. However, if id was unsigned long or unsigned long long, and sizeof(long) > sizeof(int) then you'd be vulnerable to some very odd behaviour. The observation that the explicit return ±1 mechanism always works is still accurate; the sweeping "subtraction doesn't work if the comparison of two unsigned quantities" is not strictly accurate.

[beta]

Ok I understand. Thanks a lot for the explanation.