Quickselect
Partition like quick sort, but only follow the side that holds the k-th value.
Rotate, Partition, Select: The 4th smallest
The pivot sits at index 3, so it is the 4th smallest. That is exactly what we wanted.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n^2)
- Space
- O(1)
Median-of-medians pivot guarantees O(n) worst case.
Properties
- Yes: Comparison based
- No: Stable
- Yes: In place
- No: Adaptive
- No: Online
Before this
Related
Taught by the same lesson
Rotate, Partition, Select covers these too, in the same run.