#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;
 }
}