Auswahlalgorithmen

Auswahlalgorithmen sind Algorithmen, die das k-te kleinste Element einer endlichen Folge oder eines Datensatzes finden, ohne die gesamte Eingabe vollständig zu sortieren. Sie liefern den k-ten Rang oder das entsprechende Quantil und arbeiten auf der Ordnung der Elemente. Die Algorithmen können deterministisch oder randomisiert sein und auf dem Hauptspeicher oder externen Speicher arbeiten.

Eine zentrale Familie ist Quickselect, eine partitionierende Rekursionsmethode, die wie Quicksort funktioniert, aber nur die Teilmenge bearbeitet, die das k-te Element enthält. Erwartet läuft Quickselect in linearem Zeitaufwand O(n) und benötigt im Normalfall nur konstanten zusätzlichen Speicher, wohingegen der Worst-Case O(n^2) betragen kann; verschiedene Pivotstrategien reduzieren die Wahrscheinlichkeit eines schlechten Falls.

Für garantiert lineare Laufzeit im schlechtesten Fall gibt es deterministische Algorithmen wie BFPRT (Blum–Floyd–Pratt–Rivest–Tarjan), auch Median-of-Medians genannt. Sie wählen systematisch einen robusten Pivot und erreichen O(n) Zeit, allerdings mit größeren Konstantenfaktoren und komplexerer Implementierung.

Es existieren auch Varianten und Erweiterungen für spezielle Umgebungen, z. B. Auswahl in externem Speicher, parallele oder verteilte Algorithmen und Streaming- bzw. Online-Ansätze, die Näherungs- oder sukzessive Schätzungen liefern, ohne die gesamte Eingabe zu halten.

Anwendungen der Auswahl umfassen die Bestimmung von Mediane, Perzentilen und anderen Rangstatistiken in Datenanalysen, robuste Statistikverfahren sowie Vorverarbeitungsschritte in Algorithmen, die auf Rangordnungen beruhen.