next up previous contents
Nächste Seite: BFPRT-Algorithmus Aufwärts: Sortieren und Selektieren Vorherige Seite: Bucket Sort   Inhalt

Selektieren

Definition:
Unter Selektieren versteht man die Suche nach dem $ k$-kleinsten Element einer $ n$-elementigen Menge.

Ansatz:
Verwende Quicksort, aber sortiere immer nur die Partition, die das $ k$-kleinste Element enthält. Dieser Algorithmus hat amortisierte Kosten $ O(n)$, aber Worst Case $ O(n^2)$.

Definition:
Der Median ist das $ floor(n/2)$-kleinste (alternativ $ ceil(n/2)$-kleinste) Element einer $ n$-elementigen Menge.

Untere Schranke:
Jeder Algorithmus zur Bestimmung des Medians benötigt min. $ 3/2n-1$ Vergleiche.



Unterabschnitte

2003-10-08