Sunday, 14 December 2014

Pin It

Widgets

Recursive QuickSort for Array of Strings


#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;
}


No comments: