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.

Have you written a function that can tell you which of two given structs has a larger or smaller id field? — sarnold
– sarnold, Commented Jan 4, 2012 at 2:09

hyde · Accepted Answer · 2013-07-21 08:36:09Z

27

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.

edited Jul 21, 2013 at 8:36

hyde

2,5954 gold badges27 silver badges51 bronze badges

answered Jan 4, 2012 at 2:15

Jonathan Leffler

759k145 gold badges961 silver badges1.3k bronze badges

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

2 Comments

beta Over a year ago

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

Jonathan Leffler Over a year ago

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.

Collectives™ on Stack Overflow

How to sort an array of structs in C?

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related