Quick Sort

Algorithm of Quick Sort

QuickSort(a,beg,end)            // a is Array
{
if(beg<end)
{
p=Partition(a,beg,end);         //Calling Procedure to Find Pivot

QuickSort(a,beg,p-1);           //QuickSort Calls Itself
QuickSort(a,p+1,end);           //(Divides the List into two Sub Lists)      
}
}


Procedure to Find Pivot :-

Partition(a,beg,end)
{
p=beg, pivot=a[beg];

for loc=beg+1 to end;
{
if(pivot>a[loc])
{
a[p]=a[loc];
a[loc]=a[p+1];
a[p+1]=pivot;

p=p+1;
}
}
return p;
}

Program in C++ --- Quick Sort

#include<iostream>
#include<conio.h> 

using namespace std;

 int Partition(int a[], int beg, int end)          //Function to Find Pivot Point
{
int p=beg, pivot=a[beg], loc;

for(loc=beg+1;loc<=end;loc++)
{
if(pivot>a[loc])
{
a[p]=a[loc];
a[loc]=a[p+1];
a[p+1]=pivot;

p=p+1;
}
}
return p;
}


void QuickSort(int a[], int beg, int end)
{
if(beg<end)
{
int p=Partition(a,beg,end);                       //Calling Procedure to Find Pivot

QuickSort(a,beg,p-1);                             //Calls Itself (Recursion)
QuickSort(a,p+1,end);                 //Calls Itself (Recursion)
}
}


void main()
{
int a[100],i,n,beg,end;

cout<<"\n------- QUICK SORT -------\n\n";
cout<<"Enter the No. of Elements : ";
cin>>n;

for(i=1;i<=n;i++)
{
cin>>a[i];
}
beg=1;
end=n;

QuickSort(a,beg,end);                           //Calling of QuickSort Function

cout<<"\nAfter Sorting : \n";
for(i=1;i<=n;i++)
{
cout<<a[i]<<endl;
}
getch();
}

Output :-

Posted in: C++, Sorting in C++