NIST

Select

(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

More information

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


Go to the Dictionary of Algorithms and Data Structures home page.

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