#include <stdio.h> #include <stdlib.h> #include <string.h> // enumeration denoting sort type enum CompareDataType { cmpStringType = 1, cmpIntType = 2 }; // Employee structure struct Employee { char *name; int age; }; // Method to swap two structures by reference. void Swap(struct Employee *first, struct Employee *second) { struct Employee temp = *first; *first = *second; *second = temp; } int IsLessThan(struct Employee *first, struct Employee* second, enum CompareDataType cmpType) { int res = 0; switch (cmpType) { case cmpStringType: res = strcmp(first->name, second->name); break; case cmpIntType: res = first->age < second->age ? -1 : (second->age < first->age); break; default: fprintf(stderr, "Invalid sort comparison type\n"); exit(EXIT_FAILURE); } return res; } // Method to get the partition index of an array. int Partition(struct Employee array[], int startIndex, int endIndex, enum CompareDataType cmpType) { struct Employee endIndexElement = array[endIndex]; int index; int tempIndex = startIndex; for(index = startIndex; index <= endIndex - 1; index++) { if(IsLessThan(&array[index], &endIndexElement, cmpType) < 0) { Swap( &array[index], &array[tempIndex]); tempIndex++; } } Swap( &array[endIndex], &array[tempIndex]); return tempIndex; } // Quicksort method void QuickSort(struct Employee array[], int startIndex, int endIndex, enum CompareDataType cmpType) { int partitionIndex; if(startIndex < endIndex) { partitionIndex = Partition(array, startIndex, endIndex, cmpType); // Now the element at partition index is fixed, we will recursively call the QuickSort method on the left and right subarrays. QuickSort(array, startIndex, partitionIndex - 1, cmpType); QuickSort(array, partitionIndex + 1, endIndex, cmpType); } } // Entry point of the program int main() { struct Employee array[] = {{"John", 45}, {"Mary", 23}, {"Celina", 79}, {"Mike", 41}}; int arraySize = 4; int index; printf("Before Sorting : \n"); for(index = 0; index < arraySize; index++) { printf("(%s, %d) ", array[index].name, array[index].age); } printf("\n"); QuickSort(array, 0, arraySize-1, cmpStringType); printf("After Sorting by name : \n"); for(index = 0; index < arraySize; index++) printf("(%s, %d) ", array[index].name, array[index].age); printf("\n"); QuickSort(array, 0, arraySize-1, cmpIntType); printf("After Sorting by age : \n"); for(index = 0; index < arraySize; index++) printf("(%s, %d) ", array[index].name, array[index].age); printf("\n"); return 0; }
Sunday, 14 December 2014
Recursive QuickSort for Array of Structures
Labels:
Sorting
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment