Sunday, 14 December 2014

Pin It

Widgets

Recursive QuickSort for Array of Characters


#include<stdio.h>
/*
* Implemented by Arjun Sunel.
*/

// Method to swap two characters by reference.
void Swap(char *first, char *second)
{
 char temp = *first;
 *first = *second;
 *second = temp;
}

// Method to get the partition index of a character array.
int Partition(char array[], int startIndex, int endIndex)
{
 int endIndexElement = array[endIndex];
 int index;
 int tempIndex = startIndex;
 
 for(index = startIndex; index <= endIndex - 1; index++)
 {
  if(array[index] <= endIndexElement)
  {
   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[] = {'d', 'a', 'c', 'b'};
 int arraySize = 4;
 int index;
  
 printf("Before sorting : \n");
 for(index = 0; index <= arraySize - 1; index++)
 {
  printf("%c ", array[index]);
 } 
 
 QuickSort(array, 0, arraySize-1);

 printf("\nAfter sorting : \n");
 for(index = 0; index <= arraySize - 1; index++)
 {
  printf("%c ", array[index]);
 } 

 printf("\n");
}


No comments: