The worst-case performance of a randomized selection algorithm is O(n2). 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:
- Select a pivot:
- Split a list of unordered items into groups of five elements each.
- Sort and find the median of all the groups.
- Repeat step 1 and step 2 recursively to obtain the true median of the list.
- Use the true median to partition the list of unordered items.
- Recurse into the part of the partitioned list that may contain the ith-smallest element.
Previously, in the random selection algorithm, we selected the first element as the pivot. We shall replace that step with a sequence of steps that enables us to obtain the true or approximate median. This will improve the partitioning of the list about the pivot:
def partition(unsorted_array...