Quicksort
Internal
Overview
Quicksort is an in-place sorting divide-and-conquer algorithm. Being an in-place sorting algorithm is considered preferable to merge sort, which has to allocate extra memory.
| Worst-case time | Θ(n2) |
| Expected running time | Θ(n lg n) |
| Best-case time | Θ(n lg n) |
Algorithm
The key idea of Quicksort is to partition an array around a pivot. The pivot is chosen randomly and it can be formally shown that randomly choosing a pivot at each step of the algorithm produces an O(n lg n) time complexity on average. Partitioning an array is discussed here: The Partition Subroutine.
After partitioning, we'll end up with three distinct sections of the array: the subarray where all elements are smaller or equal than the pivot, the pivot and the subarray where all elements are bigger than the pivot.
The partitioning is the divide phase of the divide and conquer algorithm.
The next step is to "conquer": call quicksort recursively on the first and the last section of the array. The pivot is already in the correct position and we will leave it there.
The last step, "combine", does not do anything.
Correctness
Time Complexity Analysis
QuickSort does not subdivide the problem in equal subproblems at one level, so the master theorem does not apply in its current form.
CLRS pages 174, 180.
TODO Stanford algorithm class:
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/5Tuvu/analysis-i-a-decomposition-principle
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/sIY1s/analysis-ii-the-key-insight
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/aqD1O/analysis-iii-final-calculations
Quicksort and Selection Problem
The randomized Quicksort algorithm is somewhat similar to the one used by the generic selection problem.