prev up next

Previous: Quicksort Up: Sortieren Next: Heapsort

Bestimmung des Medians

public static int select (int[] S, int k) $\{$
/* Liefert aus dem Feld $S$ das $k$-t kleinste Element. */

     int[] A, B, C;

     int n = |S|;
     if (n < 50) return k-t kleinstes Element per Hand;
     else $\{$
          zerlege S in Gruppen zu je 5 Elementen $S_{1}, S_{2}, \ldots, S_{ \frac{n}{5}}$;
          Bestimme in jeder Gruppe $S_i$ den Median $m_i$;
          Bestimme den Median der Mediane:
               m = select $(\bigcup_{i} m_{i},\frac{n}{10})$;
          A = $\{$x $ \in $ S | x < m$\}$;
          B = $\{$x $ \in $ S | x == m$\}$;
          C = $\{$x $ \in $ S | x > m$\}$;
          if (|A| >= k) return select (A, k);
          if (|A|+|B| >= k) return m;
          if (|A|+|B|+|C| >= k) return select(C, k-|A|-|B|);
     $\}$
$\}$

Beh.:
$\vert A\vert\leq \frac{3}{4} n$


d.h. mind. $\frac{1}{4}$ der Elemente von $S$ ist $\geq m$

$\Rightarrow$ höchstens $\frac{3}{4}$ der Elemente von $S$ ist $< m$

$\Rightarrow \vert A\vert\leq \frac{3}{4} n$, analog $\vert C\vert\leq \frac{3}{4} n$.

Sei $f(n)$ die Anzahl der Schritte, die die Methode select benötigt für eine Menge $S$ der Kardinalität $ n $.

Also:

\begin{displaymath}
f(n)\leq \left\{
\begin{array}{cccccl}
c &&&&& \mbox{, f\um...
...\mbox{der Mediane}&&\mbox{A \mbox{ oder }C}
\end{array}\right.
\end{displaymath}

Beh.:
$f \in O(n)$
Zeige:
$f(n)\leq 20\cdot c \cdot n$

Beweis durch Induktion:

$f(n)\leq c \leq 20 \cdot c \cdot n$ für $n < 50$

Sei bis $n - 1$ bewiesen
$f(n)$ $\leq$ $c\cdot n$ $ +$ $f(\frac{n}{5})$ $ +$ $f(\frac{3}{4}n)$  
  $\uparrow$            
  Rekursionsgl.            
  $\leq$ $c\cdot n$ $ +$ $20 \cdot c \cdot \frac {n}{5}$ $ +$ $20\cdot c\cdot \frac{3}{4}\cdot n$  
  $\uparrow$            
  Ind.-Annahme            
  $=$ $1\cdot c\cdot n$ $ +$ $4\cdot c\cdot n$ $ +$ $15\cdot c\cdot n$  
  $=$ $20\cdot c\cdot n$         q.e.d.

prev up next
Previous: Quicksort Up: Sortieren Next: Heapsort