prev up next


Previous: Quicksort Up: Sortieren Next: Heapsort

Bestimmung des Medians

static double select (Menge S, int k) {
/* Liefert aus der Menge S das k -t kleinste Element. */
/* Die Menge S habe n Elemente. k $\leq$ n . */
     Menge A, B, C;


     if (|S| < 50) return k-t kleinstes Element per Hand;
     else {
          n = |S|;
          zerlege S in Gruppen zu je 5 Elementen S1,S2,...,S$\scriptstyle{\frac{n}{5}}$ ;
          Bestimme in jeder Gruppe Si den Median mi ;
          Bestimme den Median der Mediane:
               m = select ($\bigcup_{i}^{}$mi,${\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);
          else if (|A|+|B| >= k) return m;
          else /* if (|A|+|B|+|C| >= k) */ return select(C, k-|A|-|B|);
     }
}

Beh.:
|A| $\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$ |A| $\leq$ ${\frac{3}{4}}$n , analog |C| $\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:

f (n) $\displaystyle\leq$ $\displaystyle\left\{ 
\begin{array}
{cccccl}
c &&&&& \mbox{, f\uml {u}r } n< 50...
 ...der 5er Gruppen}&&\mbox{der Mediane}&&\mbox{A \mbox{ oder }C}\end{array}\right.$

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

Beweis durch Induktion:

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

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


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