Design and Analysis of Algorithms

Go Back to List

Program to sort list using Quick sort.

 

#include<iostream.h>
#include<conio.h>

int quick(int[],int,int);
void main()
{
int a[50],beg,end,n,i,loc,top,lower[10],upper[10];
clrscr();
cout<<"Enter the no. of elements:";                                 //Input data
cin>>n;
cout<<"Enter the number ";
for(i=1;i<=n;i++)
cin>>a[i];
top=1;
lower[top]=1;                                                             // Store the boundary values of "a"
upper[top]=n;
while(top!=0)
{
beg=lower[top];                                                         // remove boundary values of sub list
end=upper[top];
top--;
loc=quick(a,beg,end);
if(beg<loc-1)                                                             // store boundary values of left sub list
{
top++;
lower[top]=beg;
upper[top]=loc-1;
}
if(end>loc+1)                                                            //store boundary values of right sub list
{
top++;
lower[top]=loc+1;
upper[top]=end;
}
}
cout<<"\n";
cout<<"\nSorted list is:";

for(i=1;i<=n;i++)
cout<<" "<<a[i];
getch();
}

int quick(int a[],int left,int right)
{
int loc,temp;
loc=left;
while(1)
{
while(a[loc]<=a[right]&&loc!=right)                     // scan from right to left
right--;
if(loc==right) return(loc);
temp=a[loc];
a[loc]=a[right];
a[right]=temp;
loc=right;
while(a[left]<=a[loc]&&loc!=left)                     // scan from left to right
left++;
if(loc==left)return(loc);
temp=a[loc];
a[loc]=a[left];
a[left]=temp;
loc=left;
}
}
 

Output:

Enter the no. of elements:5
Enter the number 23
12
10
45
34


Sorted list is: 10 12 23 34 45

Analysis of Quick Sort:

Worst case O(n2)
Average case 1.4 n log n


 

If any of you want  to submit your programs and contribute to site please mail us at:

citysuvidha@gmail.com

  Click here to have a look at  List of programs

You can download all the programs in a zip file also. For this you have to do one thing. Just register at the citysuvidha forum  and start any thread of any topic.  Once you start the thread and put your request, admin will automatically send you the desired zip file.