Implementing Quick Sort in C++

Quicksort is a sorting algorithm which picks one element at a time and places it at its correct position, during this it also places elements less than that element on its left and element greater than that element on right side.

The code below implements the Quick sort in recursive manner.

typedef vector<int> IntVect; int QuickPartition(IntVect & A, int start, int end) {     int  key = A[end];     int j = start - 1;     for (int i = start; i < end; i++)     {         if (A[i] < key)         {             int temp = A[++j];             A[j] = A[i];             A[i] = temp;         }     }     j++;     A[end] = A[j];     A[j] = key;     return j;     } void QuickSort(IntVect & A, int start, int end) {     if (start < end)     {         int pivot = QuickPartition(A, start, end);         QuickSort(A, start, pivot - 1);         QuickSort(A, pivot + 1, end);     } }

In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.