(algorithm)
Definition: A four-part algorithm to select the kth smallest element of an array. Part 1) Consider the array as groups of 5 elements; sort and find the median of each group. 2) Use Select recursively to find x, the median of the medians. 3) Next partition the array around x. 4) Let i be the number of elements in the low side of the partition. If k ≤ i, use Select recursively to find the kth element of the low side. Otherwise Select the k-ith element of the high side.
See also select and partition, select kth element, Find, MODIFIND, tournament, reservoir sampling.
Note: After [CLR90, p 190]. Sometimes called "quick select".
The number of comparisons to select the ith smallest of n numbers is n+min(i,n-i)+o(n) or Θ(n).
Author: PEB
Robert W. Floyd and Ronald L. Rivest, Expected time bounds for selection, CACM, 18(3):165-172, March 1975
Robert W. Floyd and Ronald L. Rivest, Algorithm #489 SELECT, CACM, 18(3):173, March 1975
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 January 2009.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "Select", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 January 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/select.html