#include<iostream.h>
#include<conio.h>
int a[50],upper[50],lower[50],utos,ltos,n,beg,end;
int upop(int *);
void upush(int *,int);
int lpop(int *);
void lpush(int *,int);
int quick(int *,int,int);
void main()
{
clrscr();
int loc1;
cout<<"\n Enter number of elements:";
cin>>n;
cout<<"\n Enter array:\n";
for(int i=1;i<=n;i++)
{
cout<<" a["<<i<<"]: ";
cin>>a[i];
}
beg=1;
end=n;
lpush(lower,beg);
upush(upper,end);
while(utos>0)
{
beg=lpop(lower);
end=upop(upper);
loc1=quick(a,beg,end);
if(beg<(loc1-1))
{
lpush(lower,beg);
upush(upper,(loc1-1));
}
if(end>(loc1+1))
{
lpush(lower,(loc1+1));
upush(upper,end);
}
}
cout<<"\n Sorted List:\n";
for(i=1;i<=n;i++)
{
cout<<"\n a["<<i<<"]: "<<a[i];
}
getch();
}
void upush(int *a,int item)
{
utos=utos+1;
a[utos]=item;
}
void lpush(int *a,int item)
{
ltos=ltos+1;
a[ltos]=item;
}
int upop(int *a)
{ int item;
item=a[utos];
utos=utos-1;
return(item);
}
int lpop(int *a)
{
int item;
item=a[ltos];
ltos=ltos-1;
return(item);
}
int quick(int *a,int beg,int end)
{
int left,right,temp,loc;
left=beg;
right=end;
loc=beg;
rtol:while((a[loc]<=a[right])||(loc!=right))
{
if(loc==right)
{
return(loc);
}
else
{
if(a[loc]>a[right])
{
temp=a[loc];
a[loc]=a[right];
a[right]=temp;
loc=right;
goto ltor;
}
}
right =right-1;
}
ltor: while(a[left]<=a[loc]||left!=loc)
{
if(loc==left)
{
return(loc);
}
else
{
if(a[left]>a[loc])
{
temp=a[loc];
a[loc]=a[left];
a[left]=temp;
loc=left;
goto rtol;
}
}
left=left+1;
}
}