NIST

select kth element

(classic problem)

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

Also known as selection problem, find kth least element, kth 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


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 kth 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