Sort an array of structs by different members

Question

I need to sort an array of structs each having members with different data types using qsort.

typedef struct {
 char* name;
 int age;
 float wage;
} employee;

The question is, do I have to write 3 different comparator functions for each of them or is there a nice way to implement 1 function?

If you want to sort by different members, then you need a comparator for each member. — Barmar, Mar 04 '20 at 23:21
I have to provide a user with ability to sort employees by name for example — Ilya Kozel, Mar 04 '20 at 23:21
Even if they're the same data type you need different comparators, because the comparator needs to know which member to compare, not just how to compare the values. — Barmar, Mar 04 '20 at 23:23
The only way to do it (portably) with a single comparator is to set a global variable before calling `qsort`, and then check the global variable in the comparator to see which member to compare. The non-portable solution is the `qsort_r` function, which allows additional information to be passed to the comparator. See [this question](https://stackoverflow.com/questions/39560773) for some background information about the portability problems with `qsort_r`. — user3386109, Mar 04 '20 at 23:40

score 1 · Answer 1 · edited Mar 05 '20 at 01:42

1

A comparison function appropriate for sorting objects of type employee will receive arguments that point to employee objects. That each object has members of several types affects how you would implement such a function, but that does not in itself present any reason why you would need more than one function.

int compare_employees(const void *e1, const void *e2) {
    const employee *employee1 = e1;
    const employee *employee2 = e2;

    // ... code to compare *employee1 with *employee2 ...
}

However, each comparison function defines a particular way of sorting the objects. If you want to provide for sorting on different criteria then you need a different comparison function for each method of ordering. This has nothing in particular to do with whether the members all have the same data type.

edited Mar 05 '20 at 01:42

Jonathan Leffler

730,956
141
904
1,278

answered Mar 04 '20 at 23:25

John Bollinger

160,171
8
81
157

I wanted to say I need to be able to sort employees by their name, age etc. separately – Ilya Kozel Mar 04 '20 at 23:29
1

And this answer addresses that, @IlyaKozel. – John Bollinger Mar 04 '20 at 23:29
I didn't read until the end, sorry for that. Thank you for helping me out – Ilya Kozel Mar 04 '20 at 23:30

score 1 · Answer 2 · answered Mar 04 '20 at 23:58

In any case you need to write a separate function for each data member by which the array will be sorted because within the function you need to compare values of concrete data members.

However you can write a general function that will supply the required comparison function for a call of qsort.

Here is a demonstrative program.

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

typedef struct {
 char* name;
 int age;
 float wage;
} employee;

int cmp_by_name( const void *a, const void *b )
{
    const employee *first  = a;
    const employee *second = b;

    return strcmp( first->name, second->name ); 
}

int cmp_by_age( const void *a, const void *b )
{
    const employee *first  = a;
    const employee *second = b;

    return ( second->age < first->age ) - ( first->age < second->age );
}

int cmp_by_wage( const void *a, const void *b )
{
    const employee *first  = a;
    const employee *second = b;

    return ( second->wage < first->wage ) - ( first->wage < second->wage );
}


enum SortBy { ByName, ByAge, ByWage };

int ( *select( enum SortBy sort_by ) )( const void *, const void * )
{
    int ( *cmp[] )( const void *, const void * ) = 
    {
        cmp_by_name, cmp_by_age, cmp_by_wage
    };

    switch ( sort_by )
    {
        default:
        case ByName:
            return cmp[ByName];
        case ByAge:
            return cmp[ByAge];
        case ByWage:
            return cmp[ByWage];
    }
}

int main(void) 
{
    enum { N = 3 };
    employee e[N] =
    {
        { "Tom", 18, 3500.0f },
        { "Bob", 26, 4500.0f },
        { "Jim", 28, 4000.0f }
    };

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%s, %d, %f\n", e[i].name, e[i].age, e[i].wage );
    }
    putchar( '\n' );

    qsort( e, N, sizeof( employee ), select( ByName ) );    

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%s, %d, %f\n", e[i].name, e[i].age, e[i].wage );
    }
    putchar( '\n' );

    qsort( e, N, sizeof( employee ), select( ByAge ) ); 

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%s, %d, %f\n", e[i].name, e[i].age, e[i].wage );
    }
    putchar( '\n' );

    qsort( e, N, sizeof( employee ), select( ByWage ) );    

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%s, %d, %f\n", e[i].name, e[i].age, e[i].wage );
    }
    putchar( '\n' );

    return 0;
}

The program output is

Tom, 18, 3500.000000
Bob, 26, 4500.000000
Jim, 28, 4000.000000

Bob, 26, 4500.000000
Jim, 28, 4000.000000
Tom, 18, 3500.000000

Tom, 18, 3500.000000
Bob, 26, 4500.000000
Jim, 28, 4000.000000

Tom, 18, 3500.000000
Jim, 28, 4000.000000
Bob, 26, 4500.000000

Good use of `const` and `(a>b)-(a – chux - Reinstate Monica Mar 05 '20 at 00:18 — chux - Reinstate Monica, Mar 05 '20 at 00:18

Saucy Goat · Answer 3 · 2020-03-05T00:18:33.663

This function should accomplish what you seek:

int compare_employees(const void * e1, const void * e2) {
    const employee * emp1 = (employee*)e1;
    const employee * emp2 = (employee*)e2;

    int ret1 = strcmp(emp1->name, emp2->name);

    if (ret1 == 0) {
        if (emp1->age == emp2->age) {
            float ret2 = emp1->wage - emp2->wage;

            if (ret2 == 0)
                return 0;
            else if (ret2 > 0)
                return 1;
            else
                return -1;
        } else {
            return emp1->age - emp2->age;
        }
    } else {
        return ret1;
    }
}

It first takes alphabetical order into account, then age, and finally wage.

Of course, I assumed you wanted to sort the elements in ascending order. If you want to sort them in descending order, all you'd have to do is flip the values for each comparison:

float ret2 = emp2->wage - emp1->wage; to sort employees by wage in descending order, for example.

Moreover, if you want a different priority for your sorting function (i.e. wage is more decisive than the names' alphabetical order, but the latter is still more decisive than age), arrange them differently within the if statements:

if (ret1 == 0) {
    int ret2 = strcmp(emp1->name, emp2->name);
    if (ret2 == 0)
        return emp1->age - emp2->age;
    else
        return ret2;
} else if (ret1 > 0) {
    return 1;
} else {
    return -1;
}

So, to do the different sort orders, you need different bodies to your function, or (better, and equivalently) different functions — not just a single function. — Jonathan Leffler, Mar 05 '20 at 01:46
@JonathanLeffler wouldn't they be "blocks", and not functions? — Saucy Goat, Mar 05 '20 at 01:48
Well, if you've got a mechanism such as a global variable to indicate which 'block' ([compound statement](http://port70.net/~nsz/c/c11/n1570.html#6.8.2)?) to execute, then it could be 'blocks'. But the global variable is ugly — it would be simpler (and arguably more performant, though barely measurably so) to use separate comparator functions. — Jonathan Leffler, Mar 05 '20 at 01:51

Sort an array of structs by different members

3 Answers3