//quick sort
#include<iostream.h>
#include<conio.h>
int quick(int [],int,int,int);
void main()
{
int top=-1,a[10],n=10,lower[10],upper[10],beg,end,loc;
clrscr();
cout<<"Enter the elements in array";
for(int i=0;i<10;i++)
cin>>a[i];
if(n>0)
{
top=top+1;
lower[0]=0;
upper[0]=n-1;
}
while(top!=-1)
{
beg=lower[top];
end=upper[top];
top=top-1;
loc=quick(a,n,beg,end);
if(beg<loc-1)
{
top=top+1;
lower[top]=beg;
upper[top]=loc-1;

}
if(loc+1<end)
{
top=top+1;
lower[top]=loc+1;
upper[top]=end;
}


}

cout<<"\nSorted array is";
for(i=0;i<10;i++)
cout<<"\n"<<a[i];
getch();

}
int quick(int a[],int n,int beg,int end)
{
int left,right,loc;
left=beg;
right=end;
loc=beg;
while(1)
{
while((a[loc]<=a[right]) && (loc!=right))
{
right=right-1;
}
if(loc==right)
return loc;
int temp;
if(a[loc]>a[right])
{
temp=a[loc];
a[loc]=a[right];
a[right]=temp;
loc=right;


}
while((a[left]<=a[loc]) && (left!=loc))
{
left=left+1;
}
if(loc==left)
return loc;
if(a[left]>a[loc])
{
temp=a[loc];
a[loc]=a[left];
a[left]=temp;
loc=left;
}
}
}
*********output*********
Enter the elements in array
11
2
5
3
5
88
9
93
12
16

Sorted array is
2
3
5
5
9
11
12
16
88
93