Einleitung

Gegeben: Menge S von n Elementen aus einem total geordneten Universum U, $i \in \mathbbm{N}$, $1 \leq i \leq n$.
Gesucht: i-kleinstes Element in S
Bekannt: Fälle $i=1,\ n$ (Minimum, Maximum bestimmen)
Standardalgorithmus: n-1 Vergleiche
Zeigen: Diese Anzahl ist optimal:

Beweis: Interpretiere jeden Algorithmus als Turnier. Ein Spiel wird vom kleineren Element gewonnen. Beobachtung: Jedes Element außer dem Gesamtsieger muß mindestens ein Spiel verloren haben $\Rightarrow$ n-1 Vergleiche notwendig.
$\Diamond$
Nun: Bestimmung des Vize-Meisters (bzw. zweitkleinstes Element)



Beweis: einem K.O. Turnier: (n-1) Vergleiche. Beobachtung: Das zweitkleinste Element ist unter den ,,Verlierern`` gegen das Minimum zu suchen. Deren Anzahl ist $\left\lceil \log_2 n \right\rceil$. Bestimme unter diesen Elementen wiederum das Minimum $\leadsto$ zweitkleinstes Element ($\left\lceil \log_2 n \right\rceil -1$) $\Diamond$

Literatur:

• Carroll, Lewis: Lawn Tennis Tournaments. St. Jones Garzette (Aug. 1, 1883), p. 5-6. Reprinted in the complete work of lewis Carroll. New York. Modern Librarry 1947.
• Pratt, V.R. and F.F. Yao: On lower bounds for computing the i-th largest element. Proc. 14. Anm IEEE. Swat (1973), p. 70-81.
• Knuth, D. E. Vol. 3

Definiere: $i= \lceil \frac{n}{2} \rceil$ : Median (das mittlere Element) = $\lceil \frac{n}{2} \rceil$ - kleinstes Element.