#include<iostream.h>
#include<conio.h>
int n;
int array[60];
int quick(int
left,int right)
{
int loc=left;
while(1)
{
while(array[loc]<=array[right]
&& loc!=right)
right--;
if(loc==right)
return loc;
else
{
int temp=array[right];
array[right]=array[loc];
array[loc]=temp;
loc=right;
}
while(array[loc]>=array[left]
&& loc!=left)
left++;
if(loc==left)
return loc;
else
{
int temp=array[left];
array[left]=array[loc];
array[loc]=temp;
loc=left;
}
}
}
void quicksort()
{
int lower[10],upper[10];
int top=0,beg,end,loc;
if(n>1)
{
lower[top]=0;
upper[top]=n-1;
}
while(top!=-1)
{
beg=lower[top];
end=upper[top];
top--;
loc=quick(beg,end);
if(beg<loc-1)
{
lower[++top]=beg;
upper[top]=loc-1;
}
if(loc+1<end)
{
lower[++top]=loc+1;
upper[top]=end;
}
}
}
void display()
{
for(int i=0;i<n;i++)
cout<<" "<<array[i];
}
void main()
{
clrscr();
cout<<"Number of elements :
";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Enter element
"<<i+1<<" : ";
cin>>array[i];
}
quicksort();
display();
getch();
}
1. quick sort is faster than other O(nlogn) sorting techniques.
ReplyDelete2.quick sort memory reference pattern is sequential and localised and hence works well with a cache.
3. quicksort is implemented with an in place partitioning algo.
4. it is a comparison sort and it is not stable.