#include<conio.h>
#include<iostream.h>
int
fl,el,stack1[100],stack2[100];
int
top1=0,top2=0,loc1,loc2,a[100];
void push1(int);
void push2(int);
int pop1();
int pop2();
int
divide(int,int);
void main()
{
clrscr();
int size,i,j;
cout<<"Enter size of an array
list\n ";
cin>>size;
i=1;
while(i<=size)
{
cout<<"Enter Elements ";
cin>>a[i];
i++;
}
fl=1;
el=size;
if(size>0)
{
push1(fl);
push2(el);
}
while((top1>=1) && (top2>=1))
{
fl=pop1();
el=pop2();
loc1=divide(fl,el);
if(fl<loc1-1)
{
push1(fl);
push2(loc1-1);
}
if(el>loc1+1)
{
push1(loc1+1);
push2(el);
}
}
cout<<endl<<"After Quick
sort->"<<endl;
i=0;
while(i<size)
{
cout<<"\t"<<a[i];
i++;
}
getch();
}
void push1(int
fl)
{
top1++;
stack1[top1]=fl;
}
void push2(int
el)
{
top2++;
stack2[top2]=el;
}
int pop1()
{
int x;
x=stack1[top1];
top1--;
return x;
}
int pop2()
{
int y;
y=stack2[top2];
top2--;
return y;
}
int divide(int
x,int y)
{
int lft,rgt,swap;
lft=x; rgt=y; loc2=x;
start:
while((loc2!=rgt) &&
(a[loc2]<=a[rgt]))
{
rgt=rgt-1;
}
if(loc2==rgt)
{
return loc2;
}
else
{
swap=a[rgt];
a[rgt]=a[loc2];
a[loc2]=swap;
lft=loc2+1;
loc2=rgt;
}
while((loc2!=lft) &&
(a[loc2]>a[lft]))
{
lft=lft+1;
}
if(loc2==lft)
{
return loc2;
}
else
{
swap=a[lft];
a[lft]=a[loc2];
a[loc2]=swap;
rgt=loc2-1;
loc2=lft;
}
goto start;
}
Comments
Post a Comment