AlgoScope

Quickselect

Partition like quick sort, but only follow the side that holds the k-th value.

Sorting, algorithm, intermediate
The pivot is at index 3.active 0-640112263847596i
The pivot is at index 3.active 0-640112263847596i

Rotate, Partition, Select: The 4th smallest

Decision, step 10 of 11

The pivot sits at index 3, so it is the 4th smallest. That is exactly what we wanted.

How rotate, partition, select works

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

Taught by the same lesson

Rotate, Partition, Select covers these too, in the same run.