Need help using qsort with an array of structs

Question

Now, I have seen various examples, but I don't get what they mean.

Here's my structure

typedef struct profile{
    char gender[1];
    double soc;
       . . .
} PROFILE;

where soc is social security number that I'm going to be sorting by.

I know you need a compare function, but I don't know how to come up with the exact thing I need.

Loader

double seems like a rather nonsensical type for a social security number. It should likely be char [10] (if you want to allow entry of not-strictly-numeric values) or uint32_t. – Verdieverdigris

Don't let the naysayers bug you. double may not be ideal, but it's perfectly adequate for holding a 9-digit integer value. At least you won't run into the problem of rounded fractional representations. – Gwin

@Mark Ransom: I hardly think nay-sayer is the appropriate term for pointing out incorrect design/code! Since when did a social security number have a fractional representation! – Bushman

@Mark Ransom: Social security numbers are like telephone numbers in that they are not really numbers at all but strings containing only digits. A char array is the most appropriate data type and a double is definitely wrong. – Cupreous

@Mitch Wheat, there's nothing wrong with pointing out that double isn't the best choice. It's not incorrect code though - there are no bugs that will result from that design choice, as long as the format of Social Security numbers does not change. I thought it was necessary to provide some balance. – Gwin

@JeremyP, I agree that a char array would be a better data type, but the question wasn't about that aspect. I think it's going too far to say a double is "definitely wrong". – Gwin

@Mark Ransom: I don't think there is any rule in Stack Overflow that prohibits the offering of unsolicited advice about topics not directly related to the question. If there is, I have breached it many times. Also, I disagree with you. Double is definitely wrong. – Cupreous

@JeremyP, nothing wrong with unsolicited advice, I do it too. It just struck me that the recommendations are a little too strong, implying that double simply won't work. You still seem to be saying that, and I'd like to know your rationale. The only lurking bug I've been able to imagine is losing the leading zeros. – Gwin

@Mark Ransom: Yes, it will work, but it doesn't make much sense particularly when you look at the validation requirements for a US SSN. By the way, the British equivalent to an SSN is the NI number which actually does start with two alphas. – Cupreous

Answer 1

Here is an example of using qsort for an array of structs in C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int price;
    int id;
} order;

int compare(const void *a, const void *b) {
  
    order *orderA = (order *)a;
    order *orderB = (order *)b;
  
    return (orderB->price - orderA->price);
}

int main() {
    order list[6];

    srand(time(NULL));

    printf("Before sorting\n");
    for (int i = 0; i < 6; i++) {   
        list[i].price = rand() % 10;
        list[i].id = i; 
        printf("Order id = %d Price = %d\n", list[i].id, list[i].price);            
    }

    qsort(list, 6, sizeof(order), compare);

    printf("AFTER sorting\n");
    for (int n = 0; n < 6; n++) {
        printf("Order id = %d Price = %d\n", list[n].id, list[n].price);    
    }       
    return 0;
}

Overarm

Very helpful, especially the compare(). :) – Guay

Your compare function is incorrect: the difference between prices may be larger than the range of type int. For example: -3 and INT_MAX produces INT_MAX + 3 for your expression that does not fit in type int, invokes undefined behavior and on most current hardware evaluates to a negative number although the comparison should return a positive number. – Alleviation

This orders from the biggest to the smallest. If you want the opposite you just have to change orderA and orderB on the return expression, correct? – Levorotatory

That's correct, i.e. you should change it to return(orderA->price - orderB->price) – Honeysucker

return ( (*(order *)b).price > (*(order *)a).price ? 1 : -1); concise one line may be easier to change order... – Olmsted

@Olmsted compare function should also be able to return 0 for equality. – Exaggerative

A safe compare function would be would return (orderA->price > orderB->price) - (orderA->price < orderB->price). See en.cppreference.com/w/c/algorithm/qsort for an example – Exaggerative

Answer 2

Your Soc should almost certainly not be of type double, but anyway here's an example of what a compare function needs to return:

int compare(const void *p1, const void *p2)
{
    const struct profile *elem1 = p1;    
    const struct profile *elem2 = p2;

   if (elem1->soc < elem2->soc)
      return -1;
   else if (elem1->soc > elem2->soc)
      return 1;
   else
      return 0;
}

Thanks for pointing out the const void *.

Here is a complete example (archived): Sorting Structures with the C qsort() Function

Bushman

-1 because you can't pass this to qsort without a hairy cast, the parameters should be const, and this can be written more simply as return (int)(elem1->soc - elem2->soc); – Infamous

@Mitch - Then the poster is using a weird compiler. But you fixed your code, so I retracted my downvote. – Infamous

@ChrisLutz: the simple subtraction method is incorrect in the general case. See my answer for counter examples. – Alleviation

The MS article can now be found at jeffpar.github.io/kbarchive/kb/073/Q73853 And notice the compare doesn't use void pointers. – Ideogram

Answer 3

The strict version of a comparator takes two constant void pointers:

int compare(const void *v1, const void *v2)
{
    const struct profile *p1 = v1;
    const struct profile *p2 = v2;
    if (p1->gender > p2->gender)
        return(+1);
    else if (p1->gender < p2->gender)
        return(-1);
    else if (p1->soc > p2->soc)
        return(+1);
    else if (p1->soc < p2->soc)
        return(-1);
    else
        return(0);
}

This compares the gender field first, then the soc field. This is how you handle any multipart comparison.

Habited

Your comparison function is sexist! (Also, the soc comparison could be done as return (int)(p1->soc - p2->soc);. The cast is unnecessary if the OP (sanely) changes the type of soc to an int.) – Infamous

@Chris: au contraire - my function is perfectly genteel; ladies before gentlemen, don't you know? The subtraction mechanism works as long as there can be no overflow; the comparison mechanism works regardless. – Habited

Spotted by researching a recent question, I am surprised at @ChrisLutz suggestion with his rep. +1 for JL. – Gropius

Why do you have to create pointers of the type you expect v1 and v2 to be? (Why can't they be standard variables). Why have you set the pointers to const? (I tried it without const and it worked fine.) – Rosenda

@Connor: You can make local variables of the appropriate type but that makes an unnecessary copy of what might be a large structure. The code isn't going to modify what it looks at (and mustn't modify it) so the pointers should be to constant data. The const pointers in the interface are mandated by the standard. You can cast away const-ness, but why would you want to do so? It will work, but it isn't as safe. – Habited

Answer 4

To sort the array, use qsort() and pass a comparison function.

Here is one that produces the correct result for all possible values of the price member:

typedef struct profile {
    char gender[1];
    double soc;
    int price;
    ...
} PROFILE;

int compare_price(const void *a, const void *b) {
    const PROFILE *oa = a;
    const PROFILE *ob = b;

    return (oa->price > ob->price) - (oa->price < ob->price);
}

int compare_soc(const void *a, const void *b) {
    const PROFILE *oa = a;
    const PROFILE *ob = b;

    return (oa->soc > ob->soc) - (oa->soc < ob->soc);
}

Notes:

• the simple subtraction of values produces incorrect results if the difference does not fit in the int type. For example -2 and INT_MAX cannot be correctly compared with the subtraction method. It would not work for floating point values either.

• the above method can be used for all comparable types, including double except for NaN.

If you wish to handle NaN, here is how to group them at the end:

#include <math.h>

int compare_soc_nan_at_the_end(const void *a, const void *b) {
    const PROFILE *oa = a;
    const PROFILE *ob = b;

    if (isnan(oa->soc)) {
        return isnan(ob->soc) ? 0 : 1;
    } else
    if (isnan(ob->soc)) {
        return -1;
    } else {
        return (oa->soc > ob->soc) - (oa->soc < ob->soc);
    }
}

Alleviation