tournament

(algorithm)

Definition: Find the maximum of a set of n elements in log n "rounds" (passes) by "playing" (comparing) pairs of elements and advancing the winner (greater) of each pair to the next round. It takes n-1 comparisons, like linear search, but may be parallelized, extended to also find the second greatest element, etc.

See also select k^th element, select and partition.

Note: The second greatest element can be found with log n - 1 additional comparisons.

Author: GS

Implementation

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

Entry modified 17 December 2004.
HTML page formatted Mon Sep 11 09:46:08 2006.

Cite this as:
Gopinath Srinivasan, "tournament", 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.nist.gov/dads/HTML/tournament.html