(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

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 Wed Mar 13 12:42:46 2019.

Cite this as:

Paul E. Black, "select k^{th} element", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 14 January 2009. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/selectkth.html