It is also called Partition Exchange sort. As the name suggests Quick Sort sorts very quickly. When implemented in a proper way, it can be two or three times faster than its competitors mergesort and heapsort. It is based on the rule of Divide and Conquer. It was developed by Tony Hoare in 1959.
This algorithm divides the list into 3 parts:
1. Elements less than the pivot element.
2. Pivot element.
3. Elements greater than the pivot element.
Pivot (Special value) may be the first, middle or last element, pivot divides the array into two parts after each pass, values on the left hand side of pivot are less or equal to pivot and those on the right hand side are greater than the pivot value.
EXAMPLE
#include <iostream>
using namespace std;
void Quick_sort(int a[], int lb, int ub)
{
int L,R,X,temp;
if(lb>=ub)
return;
L=lb;
R=ub;
X=a[lb];
while(L<R)
{
while(a[L]<=X && L<R)
++L;
while(a[R]>X)
--R;
if(L<R)
{
temp=a[L];
a[L]=a[R];
a[R]=temp;
}
}
a[lb]=a[R];
a[R]=X;
Quick_sort(a,lb,R-1);
Quick_sort(a,R+1,ub);
}
int main()
{
int a[10],i;
cout<<"ENTER THE ELEMENTS:\n";
for(i=0;i<10;i++)
{
cin>>a[i];
}
Quick_sort(a,0,9);
cout<<"SORTED ELEMENTS:\n";
for(i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
}
OUTPUT
