7

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.

beta
  • 2,583
  • 15
  • 34
  • 46
  • 6
    Have you written a function that can tell you which of two given structs has a larger or smaller `id` field? – sarnold Jan 04 '12 at 02:09

1 Answers1

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.

hyde
  • 2,525
  • 4
  • 27
  • 49
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • Many thanks for your answer, I'm going to try this code right now. – beta Jan 04 '12 at 02:37
  • 1
    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. – Jonathan Leffler Jan 04 '12 at 02:52