Sort an array using multiple sorting criteria (QuickSort)

Question

I am trying to figure out how (using the quicksort algorithm) to sort an array of structure according to 2 criteria. For example, I had a structure:

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 want to sort the elements first by gender, then the identifiers in ascending order. An example would be all men printed first with their identifiers in order, and then all women with them. I am trying to do this without using the qsort function, but I have no idea how to check. Here is my sort 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 thought I could use strcmp, but I cannot figure out where to include it in this function.

Answer 1

Of course, you can embed the comparison function and swapper. The code below is pretty simple and relies on valid pointers, but you get this idea. I also took the liberty of shortening your high-speed operators by capturing what was in 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 

Answer 2

This is not difficult. You just need a function (or a block of code, seeing that you want it to be “hard-coded”) to compare your structures. In the code example you provided, you are comparing the current object with arr[l].id <= arr[p].id . That is, you only consider the identifier to determine where your item fits. You just need to compare using other fields at this point. It would be much more neat with the function (I gave you such a function in your previous question).

You also change the id fields when swapping - leaving the name and gender unchanged in your data elements. You have to move the whole structure.

Answer 3

Just use the built-in qsort and pass it the function of a comparator, which first compares the gender, and cope with the identification number only in the case of "connections" in the first comparison.

Answer 4

I think you need to sort your array first by gender, one for men, one for women. Then use the quicksort function to sort inside these two arrays.

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

Answer 5

 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 } 

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

Use it in your own quick sort or as a qsort comparator.