Find

(algorithm)

Definition: An algorithm to select the k^th smallest element of an array and partition the array around it. First, partition around the value of the k^th element. If the split is not at element k, move the upper or lower boundary and partition again.

See also select and partition, MODIFIND, Select.

Note: This does more swaps than MODIFIND.

Author: PEB

Implementation

analysis and comparison (Rexx)

More information

C. A. R. Hoare, Algorithm 65, FIND, CACM, 4(7):321, July 1961.

C. A. R. Hoare, Proof of a Program: FIND, CACM, 14(7):39-45, January 1971.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 17 December 2004.
HTML page formatted Wed Feb 4 11:02:21 2009.

Cite this as:
Paul E. Black, "Find", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/find.html