BFPRT-Algorithmus

Algorithmus:
Der BFPRT-Algorithmus [Blum, Floyd, Pratt, Rivest, Tarjan]:
1. Teilen der Eingabe in $floor(n/m)$ Partitionen der Länge $m$ (z.B. $m=5$, immer ungerade) sowie die restlichen Elemente in eine weitere Partition
2. Sortieren der Partitionen mit Kosten je $O(1)$ zur Bestimmung der Mediane, ges. $O(n)$
3. Median $s$ aller Mediane bestimmen: rekursiver Aufruf des BFPRT, $T(1/5 \cdot n)=O(n)$
4. Partitionieren aller Elemente $x$ in $S_1: x < s$ und $S_2: x > s$, $O(n)$
5. Rekursiver Aufruf des BFPRT-Algorithmus entweder für $S_1$ oder $S_2$, ges. $T(3/4 \cdot n)=O(n)$

Bemerkung:
Nach Bestimmung von $s$ gibt es je $floor(n/2)$ Partitionen mit kleinerem und größerem Median als $s$. Partitionen mit kleinerem Median enthalten $ceil(m/2)$ Elemente $< s$, Analoges gilt für größere Elemente.

Komplexität:
Der BFPRT-Algortimus selektiert das $k$-kleinste Element aus $n$ Elementen in $O(n)$.

Bemerkung:
Aufwand für BFPRT bei $m=5$ ist etwa $20n$, daher erst für große $n$ geeignet. Weitere Verbesserungen auf bis zu $2.95n + o(n)$ für die Praxis (noch) irrelevant.