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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 January 2009.
HTML page formatted Mon Nov 18 10:44:10 2013.
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