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.

WhozCraig · Accepted Answer · 2014-07-15T21:51:42.717

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\n", 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

kallikak · Answer 2 · 2012-11-14T05:51:07.850

1

It's not hard. You just need a function (or block of code seeing you want it "hard coded") to compare your structs. In the sample code you've given you are comparing the current object using arr[l].id <= arr[p].id. That is you are only considering id to work out where your element fits. You just need to compare using the other fields at this point. It would be much tidier with a function (I gave you such a function in your earlier question).

You are also only shifting the id fields when you swap - leaving the name and gender unchanged in your data items. You should move the whole struct.

edited Nov 14 '12 at 05:51

answered Nov 14 '12 at 05:45

kallikak

844
6
13

Ah thanks for catching that I didnt eve notice. When I am trying to switch arr[l]=arr[r] I am getting a syntax error. – bardockyo Nov 14 '12 at 06:14

score 0 · Answer 3 · answered Nov 14 '12 at 05:34

0

Just use the built-in qsort, and pass it a comparator function that compares gender first, and consults ID number only in case of "ties" in the first comparison.

answered Nov 14 '12 at 05:34

amalloy

89,153
8
140
205

Thanks, I do realize that but I am trying to see how it would work if it was hard coded, not using qsort – bardockyo Nov 14 '12 at 05:38

score 0 · Answer 4 · answered Nov 14 '12 at 05:45

0

I think you should sort your array by gender first, one for male, one for female. Then use the quicksort function to sort within those two arrays.

You can use strcmp to sort the original array into two arrays: one for male, one for female.

answered Nov 14 '12 at 05:45

It's possible to do sorting in two passes like this -- but when/if you do, it's crucial to use a stable sort (maintains the original order in case of a tie). Quicksort, at least as normally implemented for arrays, is not stable. – Jerry Coffin Nov 15 '12 at 02:45

score 0 · Answer 5 · answered Nov 14 '12 at 05:49

int compare_employee (struct employee * a, struct employee * b) {
    int diff = strcmp(a->gender, b->gender);

    if (diff) // if gender different
        return -diff; // sort descending, please double check this and reverse in case I am wrong

    return a->id - b->id; // else sort by id
}

Will output a negative number if a < b, positive if a > b, zero if they are equal.

Use it eigther in your own quicksort or as a qsort comparator.

Sorting an array using multiple sort criteria (QuickSort)

5 Answers5

Linked