Featured Post

Trie implementation in C

QuickSort implementation in C

A simple implementation for QuickSort using arrays.
This version of QuickSort involves the partitioning mechanism. In each pass we partition the array into two parts and the center point is the 'Pivot'. One part contains elements greater than 'Pivot' and other contains less than 'Pivot'.

We continue this process until the array becomes sorted.


#include <stdio.h>
#include <stdlib.h>

void display(int*,int);

void swap(int *a, int *b)
{
  *a = *a - *b;
  *b = *b + *a;
  *a = *b - *a;
}

int partition(int *arr, int start, int end)  //Partition the array
{
  int pivot = start;
  int left = start , right = end;
  int i , pivotVal = arr[pivot];
  
  while(left < right)
  {
    while(arr[left] <= pivotVal && left <=end )
      left++;
    while(arr[right] > pivotVal && right >= 0)
      right--;
    if(left < right)
      swap(&arr[left], &arr[right]);
  }

  arr[start] = arr[right];
  arr[right] = pivotVal;

  return right;
}

void quick(int *arr, int start, int end)
{
  int m;
    if(start < end)
    {
      m = partition(arr,start,end); //Pivot
      quick(arr,start,m-1);
      quick(arr,m+1,end);
    }
}



void display(int *arr,int nmem)
{
  int i;
  for(i = 0; i < nmem;i++)
    printf("%d ",arr[i]);
  printf("\n");
}

int main()
{
  int arr[]={12,32,2,56,34,23,67,122};
  int nmem = sizeof(arr)/sizeof(int);
  
  quick(arr, 0, nmem - 1);
  display(arr,nmem);  //Sorted array
}


Comments