(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
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 January 2009.
HTML page formatted Wed Feb 4 11:02:22 2009.
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.itl.nist.gov/div897/sqg/dads/HTML/selectkth.html