Quick Sort is an Sorting process which helps in sorting a list of elements.
Following Program Illustrates The Concept :
#include<iostream>
using namespace std;
int lower[10],upper[10],top=-1,loc; //stacks for keeping records of sublists
void sort(int a[],int,int); //function for performing quick sort operation
main()
{ int n,beg,end,a[20];
cout<<"Enter The No of Elements "; //taking the no of elements
cin>>n;
cout<<"Enter The Elements\n";
for(int i=0;i<n;i++)
{
cin>>a[i]; //storing the elements in array
}
beg=0; //first element
end=n-1; //last element
top++;
lower[top]=0; //pushing in stack
upper[top]=end;
while(top!=-1)
{
beg=lower[top]; //popping from stack
end=upper[top];
top--;
sort(a,beg,end); //calling quick sort
if(beg<loc-1) //if it is a left sublist
{
top++;
lower[top]=beg;
upper[top]=loc-1;
}
if(loc+1<end) //if it is a right sublist
{
top++;
lower[top]=loc+1;
upper[top]=end;
}
}
cout<<"Sorted List Is ";
for(int i=0;i<n;i++)
{
cout<<a[i]<<"\t"; //printing of sorted list
}
}
void sort(int a[],int beg,int end) //function definition
{
int left,right;
left=beg;
right=end;
loc=beg;
step:
while(a[loc]<=a[right]&&loc!=right) //scanning from right to left
{
right--;
}
if(loc==right)
{
return;
}
if(a[loc]>a[right])
{
int temp;
temp=a[loc]; //swapping values
a[loc]=a[right];
a[right]=temp;
loc=right;
}
while(a[left]<=a[loc]&&loc!=left) //scanning from left to right
{
left++;
}
if(loc==left)
{
return;
}
if(a[loc]<a[left])
{
int temp; //swapping values
temp=a[loc];
a[loc]=a[left];
a[left]=temp;
loc=left;
}
goto step; //for next search
}
Also See Program of Operations On Circular Queue Click Here
Output:
