select k^th element

(classic problem)

Definition: Find the k^th smallest element of a set. Two approaches are a modified distribution sort or select and partition.

Also known as selection problem, find k^th least element, k^th smallest element.

See also Select, MODIFIND, Find, reservoir sampling.

Note: The select-and-partition approximately divides in half the number of elements that must be considered at each step. The modified distribution sort divides by m the number of elements at each step. The latter is faster, but the former is more generally applicable.

Author: PEB

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 k^th element", 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/selectkth.html