Python Data Structures and Algorithms

Deterministic selection

The worst-case performance of a randomized selection algorithm is O(n²). It is possible to improve on a section of the randomized selection algorithm to obtain a worst-case performance of O(n). This kind of algorithm is called deterministic selection.

The general approach to the deterministic algorithm is listed here:

1. Select a pivot:
   1. Split a list of unordered items into groups of five elements each.
   2. Sort and find the median of all the groups.
   3. Repeat step 1 and step 2 recursively to obtain the true median of the list.
2. Use the true median to partition the list of unordered items.
3. Recurse into the part of the partitioned list that may contain the ith-smallest element.