Seonglae ChoDue to Blum, Floyd, Pratt, Rivest and Tarjan [1973]
There is linear time worst case algorithm. The idea is generating a good pivot recursively which drop worst cases of Randomized selection
- Divide the elements into groups of and find the median of each -element group by rote.
- Recursively select the median of the group medians to be the pivot
- Partition around the pivot . Let .
- If then return x
else if
then recursively select the th smallest element in the lower part
else recursively select the th smallest element in the upper part
Abstraction
- for big number is worse than Randomized selection
- For , worst-case time is