Description: This method is invented by hoare, considered to be fast method to sort the elements. The method is also called partition exchange sorting. The method is based on divide and conquer technique. i.e., the entire list is divided into various partitions and sorting is applied again and again on the partition.
In this method the list is divided into two baesd on an element called pivot element. Usually the first element is considerd to be the pivot element. Now move the pivot element to its correct position in the list. The elements to the left and pivot element are less that this while the elements to the right of pivot are greater than the pivot. The process is reapplied to each of these partitions till we got the sorted list of elements.
Algorithm:
Quick Sort:
1. start
2. if lowerbound < upperbound repeat through steps 3 to 13 otherwise
goto step 14
begin
3. assign lowerbound to i,upperbound to j, i to pivot
4. if i<j repeat through steps 5 to 10 otherwise goto step _
Begin
5. if a[i]<=k[pivot] and i< upperbound repeat through step 6 otherwise
goto step 7
begin
6. assign i+1 to i
end if
7. if k[j] > k[pivot] repeat through step 8 otherwise goto step 9
begin
8. assign j-1 to j
end if
9. if i< j goto step 10 other wise goto step 4
Begin
10. call function to swap k[i] and k[j]
end if
end if
11. call function to swap k[pivot] and k[j]
12. call function qsort(x,lowerbound,j-1)
13. call function qsort(x,j+1,upperbound)
end if
14. stop
Program:
#include<stdio.h>
main()
{
int x[10],i,n;
clrscr();
printf("enter no of elements:");
scanf("%d",&n);
printf("enter %d elements:",n);
for(i=1;i<=n;i++)
scanf("%d",&x[i]);
quicksort(x,1,n);
printf("sorted elements are:");
for(i=1;i<=n;i++)
printf("%3d",x[i]);
getch();
}
quicksort(int x[10],int first,int last)
{
int pivot,i,j,t;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(x[i]<=x[pivot] && i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j)
{
t=x[i];
x[i]=x[j];
x[j]=t;
}
}
t=x[pivot];
x[pivot]=x[j];
x[j]=t;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
enter no of elements:6
enter 6 elements:23
12
45
34
21
87
sorted elements are: 12 21 23 34 45 87
conclusion: The program is error free
VIVA QUESATIONS
1) Define quick sort ?
Ans:
This method is invented by hoare, considered to be fast method to sort the elements. The method is also called partition exchange sorting. The method is based on divide and conquer technique. i.e., the entire list is divided into various partitions and sorting is applied again and again on the partition.
In this method the list is divided into two baesd on an element called pivot element. Usually the first element is considerd to be the pivot element. Now move the pivot element to its correct position in the list. The elements to the left and pivot element are less that this while the elements to the right of pivot are greater than the pivot. The process is reapplied to each of these partitions till we got the sorted list of elements.
2) Efficiency of quick sort ?
Ans: O(n log n)
No comments:
Post a Comment