Explain the algorithm for QUICK sort ( partition exchange sort) and give a suitable example.
Quick sort is based on partition. It is also known as partition exchange sorting. The basic concept of quick sort process is pick one element from an array and rearranges the remaining elements around it. This element divides the main list into two sub lists. This chosen element is called pivot. Once pivot is chosen, then it shifts all the elements less than pivot to left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element.
Ex:- A list of unsorted elements are: 8 3 2 11 5 14 0 2 9 4 20
Algorithm for quick sort:
It is also known as partition exchange sort. It was invented by CAR Hoare. It is based on partition. The basic concept of quick sort process is pick one element from an array and rearranges the remaining elements around it. This element divides the main list into two sub lists. This chosen element is called pivot. Once pivot is chosen, then it shifts all the elements less than pivot to left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element.
quicksort(q)
varlist less,
pivotList, greater if
length(q) ≤ 1
return q
select a pivot value pivot from q
for each x in q except the
pivot element if x < pivot
then add x to less
if x ≥ pivot then add x
to greater add pivot to
pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
Advantages of quick sort:
- This is faster sorting method among all.
- Its efficiency is also relatively good.
- It requires relatively small amount of memory.
Disadvantages of quick sort:
It is complex method of sorting so, it is little hard to implement than other sorting methods.
#include <stdio.h>
void quicksort(int[ ],int,int);
void main( )
{
int low, high, pivot, t, n, i, j, a[10];
clrscr( );
printf("\nHow many elements you want to sort ? ");
scanf("%d",&n);
printf("\Enter elements for an array:");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
low=0;
high=n-1;
quicksort(a, low, high);
printf("\After Sorting the elements are:");
for(i=0; i<n; i++)
printf("%d ",a[i]);
getch( );
}
void quicksort(int a[ ],int low,int high)
{
int pivot,t,i,j;
if(low<high)
{
pivot=a[low];
i=low+1;
j=high;
while(1)
{
while(pivot>a[i] && i<=high)
i++;
while(pivot<a[j] && j>=low)
j--;
if( i < j )
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
else break;
}
a[low]=a[j];
a[j]=pivot;
quicksort(a,low,j-1);
quicksort(a,j+1,high);
}
getch();
}