Sorting – Quick Sort (Partition Exchange Sort)
Suppose x be an array, n is the number of elements. Choose an element from a specific position within the array. Array x is partitioned so that y is placed into position j, and the following conditions hold:
1) Each of the elements in position 0 through (j-1) is less than or equal to y.
2) Each of the elements in position (j+1) through (n-1) is greater than or equal to y.
Example:
Let key element = lb = arr[0] = 14
Now i will move forward until arr[i] becomes greater than key value. Finally i is positioned at 15.
Similarly j shifts backward until arr[j] becomes lower than key value. Finally j is positioned at 11.
Now, swap(arr[i],arr[j]);
Now the same set of routines are again called with new values of i and j i.e. lb and ub.
Now i is positioned at 15, since 8 is less than 14. Similarly j is positioned at 8.
Now i<=j condition is false i.e. upper bound is lower than lower bound which must be higher.
Now swap(arr[j],key);
Then all smaller values (for key) are aligned to left and greater values to right. Now partition it in two parts (8,7,3,11) and (15,16,25). Repeat the same process again. Finally combine all segments – (left, key, right) to obtain sorted array.
Program to implement Quicksort:
#include <stdio.h>
#include <conio.h>
#define MAX 10
void quicksort(int arr[],int lb,int ub);
int partition(int arr[],int lb,int ub);
void main()
{
int arr[MAX],i,n,keyelement,lb,ub;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
printf(“\nEnter elements?”);
for(i=0;i<n;i++)
{scanf(“%d”,&arr[i]);
}
keyelement = arr[0];
lb=0;
ub=(n-1);
quicksort(arr,lb,ub);
printf(“\nSorted Array is: “);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}
void quicksort(int arr[],int lb,int ub)
{
int j;
if(lb>=ub)
return;
j=partition(arr,lb,ub);
quicksort(arr,lb,j-1);
quicksort(arr,j+1,ub);
return;
}
int partition(int arr[],int lb,int ub)
{
int a,down,temp;
a=arr[lb];
down=lb;
while(lb<ub)
{while((arr[lb]<=a) && (lb<ub))
lb++;
while(arr[ub]>a)
ub–;
if(lb<ub)
{temp=arr[lb];
arr[lb]=arr[ub];
arr[ub]=temp;
}
}
temp=arr[ub];
arr[ub]=a;
arr[down]=temp;
return ub;
}