CODEWITHSUNDEEP
csorting
beta
beta

Reputation: 2633

How to sort an array of structs in C?

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.

Upvotes: 7

Views: 27015

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 753455

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.

Upvotes: 27

Related Questions