CS341 Study Guide - Eaves, Selection Algorithm, Sorting Algorithm
Document Summary
Selection in deterministic linear time. (see clrs, section 9. 3) In the selection problem, the goal is to determine the i"th smallest element from an unsorted list of n elements in linear time. deterministic here means that no random numbers are used. To make life easier, we assume that all the elements are distinct. This is not crucial, and a small modification makes it work for any list. The algorithm we present is due to blum, floyd, pratt, rivest, and tarjan (1973). (it is interesting to note that all the authors, except pratt, went on to win turing awards, computer science"s highest award. ) The idea is quite similar to that in randomized-select, but instead of choosing a partition randomly, we partition around an element that we have chosen very cleverly. Here"s the idea: we split our list of n numbers into floor(n/5) groups of 5 elements, and one additional group of at most. This gives us a list of floor(n/5) medians.
