c - Sorting an array using multiple sort criteria (QuickSort)

Question

I am trying to find out how (using a quicksort algorithm) to sort an struct array by 2 criterias. For example say I had a struct of:

struct employee{
   char gender[12];
   char name[12];
   int id;
};

Say my input is:

struct employee arr[3]=
{
    {"male","Matt",1234},
    {"female","Jessica",2345},
    {"male","Josh",1235}
};

I am wanting to sort the elements by gender first then the IDs in ascending order. An example would be have all the males printed first with their IDs in order and then all the females with theirs. I am trying to do this without using the qsort function but I havent the slightest idea how to check . Here is my sorting function:

void quicksort(struct employee *arr, int left, int right)
{
    int pivot, l, r, temp;
    if(left < right)
    {
        p = left;
        l = left;
        r = right;
        while(l < r)
        {

            while(arr[l].id <= arr[p].id && l <= right)
                l++;
            while(arr[r].id > arr[p].id && r >= left)
                r--;

            if(l < r)
            {
                temp = arr[l].id;
                arr[l].id = arr[r].id;
                arr[r].id = temp;
            }
        }


        temp = arr[r].id;
        arr[r].id = arr[p].id;
        arr[p].id = temp;

        quicksort(arr, left, r-1);
        quicksort(arr, r+1, right);
    }
}

Any suggestions? I was thinking I could use strcmp but I cant figure out where to include it within the function.

Answer 1

You can certainly inline the comparison function, and a swapper for that matter. This code below is pretty basic and relies on valid pointers, but you'l get the idea. I also took the liberty of trimming down your quicksort, fixing what was off along the way (I hope).

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

// employee record
struct employee
{
    char gender[12];
    char name[12];
    int id;
};

// swap employee records
void swap_employee(struct employee *left, struct employee *right)
{
    struct employee tmp = *right;
    *right = *left;
    *left = tmp;
}

// compare employee records
int compare_employee(const struct employee* left,
                     const struct employee* right)
{
    int gender = strcmp(left->gender, right->gender);
    return (gender ? gender : (left->id - right->id));
}

// quicksort for employees
static void quicksort_(struct employee *arr, int left, int right)
{
    struct employee p = arr[(left+right)/2];    // as good as any
    int l = left, r = right;   // movable indicies

    while (l <= r)
    {
        while (compare_employee(arr+l, &p) < 0)
            ++l;
        while (compare_employee(arr+r, &p) > 0)
            --r;
        if (l <= r)
        {
            swap_employee(arr+l, arr+r);
            ++l; --r;
        }
    }

    if (left < r)
        quicksort_(arr, left, r);
    if (l < right)
        quicksort_(arr, l, right);
}

// exposed API
void quicksort(struct employee *arr, int count)
{
    if (arr && (count>0))
        quicksort_(arr, 0, count-1);
}

/* sample usage */
int main(int argc, char *argv[])
{
    struct employee arr[]=
    {
        {"male","Matt",1234},
        {"female","Jessica",2345},
        {"male","Josh",1235},
        {"female","Betsy",2344},
        {"male","Roger",1233}
    };

    quicksort(arr, sizeof(arr)/sizeof(arr[0]));

    for (int i=0;i<sizeof(arr)/sizeof(arr[0]);++i)
        printf("%s, %s, %d
", arr[i].gender,arr[i].name, arr[i].id);

    return EXIT_SUCCESS;
}

Results

female, Betsy, 2344
female, Jessica, 2345
male, Roger, 1233
male, Matt, 1234
male, Josh, 1235