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 kth element, select and partition.
Note: The second greatest element can be found with log n - 1 additional comparisons.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 17 December 2004.
HTML page formatted Mon Mar 5 14:59:20 2018.
Cite this as:
Gopinath Srinivasan, "tournament", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/tournament.html