#include<stdio.h> #include<string.h> /* * Implemented by Arjun Sunel. */ // Method to swap two strings by reference. void Swap(char **first, char **second) { char *temp = *first; *first = *second; *second = temp; } // Method to get the partition index of an array. int Partition(char* array[], int startIndex, int endIndex) { char *endIndexElement = array[endIndex]; int index; int tempIndex = startIndex; for(index = startIndex; index <= endIndex - 1; index++) { if(strcmp(array[index], endIndexElement) < 0) { Swap( &array[index], &array[tempIndex]); tempIndex++; } } Swap( &array[endIndex], &array[tempIndex]); return tempIndex; } // Quicksort method void QuickSort(char* array[], int startIndex, int endIndex) { int partitionIndex; if(startIndex < endIndex) { partitionIndex = Partition(array, startIndex, endIndex); // 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); QuickSort(array, partitionIndex + 1, endIndex); } } // Entry point of the program int main() { char* array[] = {"dog", "dose", "apple", "baby", "den", "deck"}; int arraySize = 6; int index; printf("Before Sorting : \n"); for(index = 0; index < arraySize; index++) { printf("%s ", array[index]); } printf("\n"); QuickSort(array, 0, arraySize-1); printf("After Sorting : \n"); for(index = 0; index < arraySize; index++) { printf("%s ", array[index]); } return 0; }
Sunday, 14 December 2014
Recursive QuickSort for Array of Strings
Labels:
Sorting
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment