(classic problem)
Definition: Given an array A of n elements and a positive integer k ≤ n, find the kth smallest element of A and partition the array such that A[1], ..., A[k-1] ≤ A[k] ≤ A[k+1], ..., A[n].
See also select kth element, Select, MODIFIND, Find.
Note: Algorithms to solve this problem are often used in sort algorithms or to find the median of a set. These can be easily changed to find the kth largest element.
Author: VZ
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 31 July 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Vladimir Zabrodsky, "select and partition", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 31 July 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/selectAndPartition.html