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 E. Black.
Entry modified 14 January 2009.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "select kth element", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 January 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/selectkth.html