Experiment No: 07
1. Experiment vision:Write a program to study and implement
Quick Sort.
2.
OBJECTIVE: Program to implement quicksort in c
programming.
3. THEORY:
Quicksort is a divide and conquer algorithm.
Quicksort first divides a large list
into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. The
steps are:
- Pick an element, called a pivot,
from the list.
- Reorder the
list so that all elements with values less than the pivot come before the
pivot, while all elements with values greater than the pivot come after it
(equal values can go either way). After this partitioning, the pivot is in
its final position. This is called the partition operation.
- Recursively apply the
above steps to the sub-list of elements with smaller values and separately
the sub-list of elements with greater values.
4. ALGORITHM:
QuickSort(a,beg,end) // a is Array
{
if(beg<end)
{
p=Partition(a,beg,end); //Calling Procedure to Find Pivot
QuickSort(a,beg,p-1);
//QuickSort Calls Itself
QuickSort(a,p+1,end); //(Divides the List into two Sub
Lists)
}
}
Procedure to Find Pivot
:-
Partition(a,beg,end)
{
p=beg, pivot=a[beg];
forloc=beg+1 to end;
{
if(pivot>a[loc])
{
a[p]=a[loc];
a[loc]=a[p+1];
a[p+1]=pivot;
p=p+1;
}
}
return p;
}
4. PROGRAM:
#include<stdio.h>
int partition(int a[], int beg, int
end) //function to find pivot
point
{
int p=beg, pivot=a[beg], loc;
for(loc=beg+1;loc<=end;loc++)
{
if(pivot>a[loc])
{
a[p]=a[loc];
a[loc]=a[p+1];
a[p+1]=pivot;
p=p+1;
}
}
return p;
}
void quicksort(int a[],int beg, int end)
{
if(beg<end)
{
int p=partition(a,beg,end); //calling procedure to
find pivot
quicksort(a,beg,p-1); //calls itself
(recursion)
quicksort(a,p+1,end); //calls itself (recursion)
}
}
void main()
{
int a[100],i,n,beg,end;
printf("\n------- quick sort
-------\n\n");
printf("enter the no. Of elements :
");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
beg=1;
end=n;
quicksort(a,beg,end); //calling of quicksort
function
printf("\nafter sorting : \n");
for(i=1;i<=n;i++)
{
printf("\n%d",a[i]);
}
}
5. OUTPUT:
------------------------------------------
------------------------------------------
6. conclusion:
Thus we studied quick sort
method and executed successfully.
7. REMARK:
One of the fastest sorting
algorithms.
8. Discussion Questions:
1) what
is quicksort? How are they created?
_________________________________________________________________________________________________________________________________________________________
2)
What are the advantages and disadvantages of quicksort?
______________________________________________________________________________________________________________________________________________________
3) What is the complexity of quicksort?
No comments:
Post a Comment