Quick-sort algorithm is based on divide and conquer approach. Quick sort is efficient sorting algorithm from merge sort. In quick sort following procedure is follow
At first the given array is divided into sub arrays and each sub array is sorted. In this we no need to combine sub arrays because of the sub arrays is already sorted. In quick sort division is takes such as the we no need to combine them later.
At first the given array is divided into sub arrays and each sub array is sorted. In this we no need to combine sub arrays because of the sub arrays is already sorted. In quick sort division is takes such as the we no need to combine them later.
Complexity of quick sort is as
Quick sort complexity in different case is different. means in worst case complexity is @(n2) and in Best case O(n log n) and in average case O(n log n).
Quick sort complexity in different case is different. means in worst case complexity is @(n2) and in Best case O(n log n) and in average case O(n log n).
Implementation of quick sort in Optimized manner is as:
/* by www.computersciencearticle.in */ #include <conio.h> #include <stdio.h> void quick(int [],int,int); int part(int [],int ,int ); void main() { int i,n,a[200],p,r; clrscr(); printf(" enter the size of array "); scanf("%d",&n); printf("enter the array elements of array"); for(i=1;i<=n;i++) scanf("%d",&a[i]); quick(a,1,n); printf("the sorted array is "); for(i=1;i<=n;i++) printf(" %d",a[i]); getch(); } void quick(int a[],int p,int r) { int q; if(p<r) { q=part(a,p,r); quick(a,p,q-1); quick(a,q 1,r); } } int part(int a[],int p,int r) { int x=a[r],i=p-1,temp,j; for(j=p;j<=r;j ) { if(a[j]<=x) { i=i 1; temp=a[i]; a[i]=a[j]; a[j]=temp; } } return i; }
Source Code: optimize quick sort
Output:-
Let the array is A=< 55, 88, 77, 99, 66, 44, 2, 100, 889, 52 >
Output of Quicksort algorithm problem in c language |