Here you will get program for quick sort in C++.
Quick Sort is one of the most efficient sorting algorithm whose best, worst and average case time complexities are O (n log n), O (n2) and O (n log n) respectively.
How it works?
1. We first pick a pivot element. There are various ways to pick a pivot element.
- Pick first element
- Pick last element
- Pick a random element
- Pick median element
So we can use anyone of above methods to pick the pivot element. In the program given below I have picked first element as pivot.
2. Now all the elements smaller than pivot are placed at its left while elements bigger are placed at right.
3. Repeat the above two steps recursively for both half.
Below is the program to implement this algorithm in C++.
Program for Quick Sort in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> using namespace std; void quick_sort(int[],int,int); int partition(int[],int,int); int main() { int a[50],n,i; cout<<"How many elements?"; cin>>n; cout<<"\nEnter array elements:"; for(i=0;i<n;i++) cin>>a[i]; quick_sort(a,0,n-1); cout<<"\nArray after sorting:"; for(i=0;i<n;i++) cout<<a[i]<<" "; return 0; } void quick_sort(int a[],int l,int u) { int j; if(l<u) { j=partition(a,l,u); quick_sort(a,l,j-1); quick_sort(a,j+1,u); } } int partition(int a[],int l,int u) { int v,i,j,temp; v=a[l]; i=l; j=u+1; do { do i++; while(a[i]<v&&i<=u); do j--; while(v<a[j]); if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } }while(i<j); a[l]=a[j]; a[j]=v; return(j); } |
Output
How many elements?6
Enter array elements:9 15 6 7 10 12
Array after sorting:6 7 9 10 12 15
interesting code but is not actually giving what was expected after sorting.please will be happy if it can be enhanced more…..thanks
in partition function
u have initialized i = l and j = u+1
instead, it should be i= l+1 and j=u
I am getting an error near the line int 1,int u and it telling that expected ‘,’ , ‘… ‘ declaration missing.could you help me out.
Nice its working. Please can you mention what does variables j,v,u stand for?
Simply Thanks a lot!
please make your code a little more elaborate, won’t do any good if you don’t use good programming practices if people can’t understand your code
Thanksss a lotttt…..nice job🙏🙏👌👌
thank u a lot
Thank you very much