Quick Sort

Sep 22, 2012 · Comments
code sorting algo c++

Quick Sort is an efficient divide and conquer algorithm performed in two phases - partition and sorting phase.

Here are few pointers to remember about Quick Sort:

Partitioning places all the elements less than the pivot in the left part of the array and greater elements in the right part
Pivot element stays in its place
After partitioning no element moves to the other side, of the pivot
* This allows you to sort the elements, to the left or right of the pivot, independent of the other side
Complexity is O(n log n)
Often fast for small arrays with a few distinct values, repeated many times
It is a conquer-and-divide algo; with most of the work happening during partitioning phase
If you had to choose the optimum pivot then it should the median of the given array
Not a stable sort

Testing Notes

Currently we have only one version of the code. We may try to do another version that is not recursive because putting the functions on stack will take up some memory and time
Another version could be trying to use the pivot from the middle and then compare how do the random numbers compare against the sorted numbers

As usual the code is available here: