Sunday, 14 December 2014

Pin It

Widgets

Recursive MergeSort for Array of Characters


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

// Merging the sorted left and right subarrays.
void Merge(char array[], int startIndex, int midIndex, int endIndex)
{
 int leftSubArraySize = (midIndex - startIndex) + 1 ;
 int rightSubArraySize = (endIndex - midIndex);
 
 char Left[leftSubArraySize], Right[rightSubArraySize];
 
 int i, j, k;
 
 for( i = 0; i < leftSubArraySize; i++)
 {
  Left[i] = array[startIndex + i];
 }
 
 for( j = 0; j < leftSubArraySize; j++)
 {
  Right[j] = array[midIndex + j + 1];
 }
 
 i = 0;
 j = 0;
 k = startIndex;
 
 while(i < leftSubArraySize && j < rightSubArraySize)
 {
  if(Left[i] <= Right[j])
  {
   array[k] = Left[i];
   i++;
  }
  else
  {
   array[k] = Right[j];
   j++;
  }
  
  k++;
 }
 
 while(i < leftSubArraySize)
 {
  array[k] = Left[i];
  i++;
  k++;
 }
 
 while(j < rightSubArraySize)
 {
  array[k] = Right[j];
  j++;
  k++;
 }
}

// MergeSort method
void MergeSort(char array[], int startIndex, int endIndex)
{
 if(startIndex < endIndex)
 {
  int midIndex = (startIndex + (endIndex - startIndex)/2);
  
  // recursively call the MergeSort method on the left and right subarrays.
  MergeSort(array, startIndex, midIndex);
  MergeSort(array, midIndex + 1, endIndex);
  Merge(array, startIndex, midIndex, 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]);
 } 
 
 MergeSort(array, 0, arraySize-1);

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

 printf("\n");
}


No comments: