Definition:
Unter Selektieren versteht man die Suche nach dem -kleinsten Element einer -elementigen Menge.
Ansatz:
Verwende Quicksort, aber sortiere immer nur die Partition, die das -kleinste Element enthält.
Dieser Algorithmus hat amortisierte Kosten , aber Worst Case .
Definition:
Der Median ist das
-kleinste (alternativ -kleinste) Element einer -elementigen Menge.
Untere Schranke:
Jeder Algorithmus zur Bestimmung des Medians benötigt min. Vergleiche.