Partition Exchange Sort

The most powerful sorting algorithm is quicksort. It uses the policy of divide and conquers. It is also known as a partition exchange sort. In Quicksort we divide the original list into two sublists.

Quicksort algorithm

Quicksort time complexity

Quicksort implementation

#include <stdio.h>

int split(int*,int,int);
int main( )
{
   int arr[5]={8,5,1,6,3};
   int i ;
   void quicksort(int*,int,int);
   quicksort ( arr, 0, 4 ) ;
   printf ( "\nArray after sorting:\n") ;
   for(i=0;i<=4;i++ )
   printf ( "%d ", arr[i] ) ;
   return 0;
}

void quicksort(int a[],int lower,int upper)
{
  int i ;
  if(upper>lower)
  {
    i=split(a,lower,upper);
    quicksort(a,lower,i-1);
    quicksort(a,i+1,upper ) ;
  }
}

int split (int a[],int lower,int upper )
{
  int i,p,q,t ;
  p=lower+1;
  q=upper;
  i=a[lower] ;//i=*(a+lower);
  while(q>=p)
  {
    while(a[p]<i)
      p++ ;

    while(a[q]>i)
      q-- ;

    if (q>p )
    {
      t=a[p] ;
      a[p]=a[q];
      a[q] = t ;
    }
  }
    t=a[lower] ;
    a[lower]=a[q] ;
    a[q]=t;
   return q ;
}

Analysis

The time requirement of quicksort depending on the position of the key in the list, how the key is dividing the list into sublists. It may be an equal division of list or maybe it will not divide also.