Algorithm/Pseudo-code For Quicksort:
/* Double-Click To Select Code */ function quicksort('array') if length('array') ≤ 1 return 'array' // an array of zero or one elements is already sorted select and remove a pivot value 'pivot' from 'array' create empty lists 'less' and 'greater' for each 'x' in 'array' if 'x' ≤ 'pivot' then append 'x' to 'less' else append 'x' to 'greater' return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls
Here is an Image depicting Quick Sort: |
In-place partition in action on a small list. The boxed element is the pivot element, blue elements are less or equal, and red elements are larger. |
C++ Program For Quick Sort:
/* Double-Click To Select Code */ #include<iostream.h> #include<conio.h> using namespace std; int part(int low,int high,int *a) { //Function for partitioning array int i,h=high,l=low,p,t; //p==pivot p=a[low]; while(low<high) { while(a[l]<p) { l++; } while(a[h]>p) { h--; } if(l<h) { t=a[l]; a[l]=a[h]; a[h]=t; } else { t=p; p=a[l]; a[l]=t; break; } } return h; } void quick(int l,int h,int *a) { int index,i; if(l<h) { index=part(l,h,a); quick(l,index-1,a); quick(index+1,h,a); } } void main() { int a[100],n,l,h,i; cout<<"Enter number of elements:"; cin>>n; cout<<"Enter the elements (Use Space As A Separator):"; for(i=0;i<n;i++) cin>>a[i]; cout<<"\nInitial Array:\n"; for(i=0;i<n;i++) { cout<<a[i]<<"\t"; } h=n-1; l=0; quick(l,h,a); cout<<"\nAfter Sorting:\n"; for(i=0;i<n;i++) { cout<<a[i]<<"\t"; } getch(); }
Output of Program:
Please Comment If You Liked This Post !!
This article uses material from the Wikipedia article Quick Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0
Do you like this post? Please link back to this article by copying one of the codes below.
URL: HTML link code: Forum link code: