Quick Sort

Quick Sort: The Quick sort Algorithm is the most popular and widely used

sorting algorithm developed by C.A.R Hoare in 1992. This algorithm tends be

the quickest in the average case among all the sorting technique.

It works on divide and conquer strategy. In divide and conquer policy the the problem is divided into smaller subproblems repeatedly until we reach the

smaller size subproblems whose solution is easy to find.

#include<iostream> using namespace std; template <class T> int partition(T a[], int start, int end) { T pivot = a[end]; int pindex = start; for(int i=start;i<end;i++) { if(a[i]<=pivot) { swap(a[i],a[pindex]); pindex++; } } swap(a[pindex],a[end]); return pindex; } template<class T> int quicksort(T a[], int start, int end) { if(start<end) { int pindex = partition(a,start,end); quicksort(a,start,pindex-1); quicksort(a,pindex+1,end); } } template <class T> void read(T a[], int n) { for(int i=0;i<n;i++) { cout<<"Enter Elements:"; cin>>a[i]; } } int main() { int a[50]; int size; cout<<"Enter the size of the array:"; cin>>size; read(a,size); quicksort(a,0,size-1); for(int i=0;i<size;i++) { cout<<" "<<a[i]; } }