 |
| http://en.wikipedia.org/wiki/Quicksort The boxed element is the pivot element, blue elements are less or equal, and red elements are larger. |
Use of Partitioning to cut the size of data down and then sorting based on one element (pivot).
Similar idea to Merge sort but we cut down on the space requirement.
Effectively, elements less than pivot will go on one side and elements greater than pivot will go on the another.
The key idea here is maintaining three different regions of the array (done in place to cut down on space requirement).
- Area smaller than pivot
- Area larger than pivot
- Unexplored area.
Interestingly the pivot ends up in the correct sorted order after the first partition step.
Best Case: O(n lg n) n partitioning steps. Recursive tree with lg n levels.
Worst Case: O(n^2) If everything is sorted we will have to search the list for each key -- performance is worse than merge or heap sort.
Worst case the partitions will look like n - 1 then n - 2 ....2 this will result in quadratic time.
Best pseudocode I found was at http://en.wikipedia.org/wiki/Quicksort.
Implementation here:
