Quickselect
Partition like quick sort, but only follow the side that holds the k-th value.
Decision · step 10 of 11Rotate, Partition, Select: The 4th smallest
The pivot sits at index 3, so it is the 4th smallest. That is exactly what we wanted.
What you will see
After each partition one side fades out; the pivot index converges on k.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n^2) |
| Space | O(1) |
Median-of-medians pivot guarantees O(n) worst case.
Properties
- ✓ comparison based
- × stable
- ✓ in place
- × adaptive
- × online
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, compare two runs.
Screen readers: Cells announce index, value and state (comparing, swapped, sorted); each step announces the comparison outcome and any move.
Reduced motion: Swaps become value crossfades with outline flashes; sorted-region growth is a static span change.
Before this
Taught by the same lesson
Rotate, Partition, Select covers these too, in the same run.