Quicksort : Different Strategy to Improve Complexity

Quicksort is a sorting algorithm used to sort a number of element. It has an average case complexity O(nlogn) and worst case complexity O(n^2). It does not use extra memory like merge sort. The complexity depends on the number of comparison of elements. Here we discuss the ways to reduce number of comparison thereby reducing complexity.

There are two procedure quicksort and partition. Partition procedure chooses a pivot and partition the elements in two half, first half having elements lower than pivot element and other half having elements greater than pivot element. Again recursively sort the two halves. The number of comparison depends upon the pivot element. The different strategy employed to reduce the number of comparison are as follows :

First : Always Choose the first element of the list as pivot and recursively sort the array.

Second: Choose last element of the list as pivot and recursively sort the array.

Third : Select median of three elements i. e. median of first element, last element and middle element as the pivot. Let the list be 5, 8,1,6,9,12. The three elements are (5,1,12) and median of these three elements is 5. This slightly increases the work in choosing median but the number of comparisons are less compared to other two approach

 The quicksort algorithm based on these three pivoting rule is implemented below :

#include<stdio.h>

int total=0;

//partition the list(considering first element as pivot)
int partition1(int arr[],int l,int r)
{
 int i=l+1,j=l+1,temp;
 for(j=l+1;j<=r;j++)
 {
  if(arr[l]>arr[j])
  {
   temp=arr[j];
   arr[j]=arr[i];
   arr[i]=temp;
   i++;
  }
  
 }
 temp=arr[l];
 arr[l]=arr[i-1];
 arr[i-1]=temp;
 return i-1;
}

//partition the list (considering last element as pivot)
int partition2(int arr[],int l,int r)
{
 int temp=arr[l];
 arr[l]=arr[r];
 arr[r]=temp;
 return partition1(arr,l,r);
}

//choosing median element as pivot
int choosepivot(int arr[],int l,int r)
{
 int first=arr[l],last=arr[r],mid,midindex;
 if((r-l+1)%2==0)
 midindex=l+(r-l+1)/2-1;
 else
 midindex=l+(r-l+1)/2;
 mid=arr[midindex];
 if((first>mid && first<last) || (first>last &&first<mid))
 return l;
 else if ((mid>first && mid<last)||(mid<first && mid>last))
 return midindex;
 else return r;
}

//partition the list (considering median element as pivot)
int partition3(int arr[], int l, int r)
{ 
 
 int pivot=choosepivot(arr,l,r);
 int temp=arr[l];
 arr[l]=arr[pivot];
 arr[pivot]=temp;
 return partition1(arr,l,r);
 
}

//quicksort1
void quicksort1(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition1(arr,l,r);
  total+=m-1-l;
  quicksort1(arr,l,m-1);
  total+=r-m+1;
  quicksort1(arr,m+1,r);
 }
}


//quicksort2
void quicksort2(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition2(arr,l,r);
  total+=m-1-l;
  quicksort2(arr,l,m-1);
  total+=r-m+1;
  quicksort2(arr,m+1,r);
 }
}


//quicksort3
void quicksort3(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition3(arr,l,r);
  total+=m-1-l;
  quicksort3(arr,l,m-1);
  total+=r-m+1;
  quicksort3(arr,m+1,r);
 }
}

//execution logic
void main()
{
 int i,n,*arr1,*arr2,*arr3,choice;
 printf("Enter No. of elements:");
 scanf("%d",&n);
 printf("\nEnter %d elements:",n);
 arr1=(int*)malloc(sizeof(int)*n);
 arr2=(int*)malloc(sizeof(int)*n);
 arr3=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 {
  scanf("%d",&arr1[i]);
  arr2[i]=arr3[i]=arr1[i];
 }
 total=0;
 quicksort1(arr1,0,n-1);
 printf("\nTotal Comparison Using Quicksort1 : %d",total);
 total=0;
 quicksort2(arr2,0,n-1);
 printf("\nTotal Comparison Using Quicksort2 : %d",total);
 total=0;
 quicksort3(arr3,0,n-1);
 printf("\nTotal Comparison Using Quicksort3 : %d",total);
 
 printf("\n\tSorted Numbers:\n-----------------------------\n");
 for(i=0;i<n;i++)
 printf("%d\t",arr1[i]);
 
}//main