Der Blum-Floyd-Pratt-Rivest-Tarjan Selektions-Algorithmus

Blum, M. and RW. Floyd and V.R. Pratt and R.L. Rivest and R.E. Tarjan: Time bounds for selection. JCSS (1973), p. 448-461.
Sei m eine kleine ungerade Zahl (etwa $5 \leq m \leq 21$). Sei $S:=\{ a_1,\dots, a_n\}$.Suche i-kleinstes Element in S. Wir betrachten folgenden Algorithmus BFPRT:

1.

Teile S in $\left\lceil \frac{n}{m} \right\rceil$ Blöcke auf, $\left\lfloor \frac{n}{m} \right\rfloor$ davon mit m Elementen

2.

Sortiere jede diese Blöcke

3.

Sei S' die Menge der $\left\lceil \frac{n}{m} \right\rceil$ Mediane der Blöcke Bestimme rekursiv den Median dieser Mediane (also das $\left\lceil \frac{\vert S'\vert}{2} \right\rceil$-kleinste Element). Nenne diesen Median s.

4.

Partitioniere $S - \{s\}$ in $S_1:=\{x \in S: x < s\}$, $S_2:=\{x \in S: x\gt s\}$. Bemerkung: $\vert S_1\vert,\ \vert S_2\vert \geq \frac{n}{4}$, falls $n \geq 3m-1$

5.

Falls $i \leq \vert S_1\vert$, bestimme rekursiv das i-kleinste Element in S₁
Falls i=|S₁|+1, gib s als Lösung zurück.
Sonst (falls |S₂| > n-i) bestimme rekursiv das (i-|S₁|-1)-kleinste Element in S₂

Komplexitätsbetrachtung (# Vergleiche im worst-case):

Sei T(n) die worst-case Anzahl von Vergleichen für |S|=n des Algorithmus BFPRT. Sei C_m die $\char93$ von Vergleichen, um m Elemente zu sortieren (z.B. $C_5=7,\ C_{11}=26)$. Es gilt:

$$\text{T}(n) \leq \underbrace{\text{T}\left(\left\lceil\frac... ...} C_m + \underbrace{\left\lfloor\frac{n}{2}\right\rfloor}_{4.}$$

Beweis: Behauptung:

$$\text{T}(n) \leq c \cdot n \hspace{1cm} \text{; wobei $c=c(m)$\space konstant ist. }$$

Behauptung ist ok, falls

$$\begin{split} \text{T}(n)\leq&\text{T}\left(\left\lceil\fra... ...frac{C_m}{m}+\frac{1}{2}}{1-\frac{3}{4}-\frac{1}{m}}\end{split}$$

Schlußbemerkung: $m=11 \leadsto c=c(m) \approx 20$ $\Diamond$