Quickselect
# Quickselect

Quickselect (englisch quick, deutsch ‚schnell‘ und to select ‚auswählen‘) ist ein Auswahlverfahren aus der Informatik, um das k-kleinste Element in einer ungeordneten Liste zu finden. Es bezieht sich auf den Quicksort-Sortieralgorithmus. Wie Quicksort wurde es von Tony Hoare entwickelt und ist daher auch als Hoare-Auswahlalgorithmus bekannt. Wie Quicksort ist es in der Praxis effizient und hat einen guten Average Case, jedoch auch eine schlechte Leistung im Worst Case. Quickselect und seine Varianten sind die am häufigsten verwendeten Selektionsalgorithmen in effizienten Implementierungen in der Praxis.
Quickselect verwendet den gleichen Gesamtansatz wie Quicksort, wählt ein Element als Pivot und teilt die Daten in zwei Teile, basierend auf dem Pivot, entsprechend kleiner oder größer als der Pivot. Anstatt jedoch, wie bei Quicksort, in beide Seiten zurückzukehren, kehrt die Schnellauswahl nur in eine Seite zurück – die Seite mit dem gesuchten Element. Dies reduziert die durchschnittliche Komplexität von ${\mathcal {O}}(n\log(n))$ auf ${\mathcal {O}}(n)$, mit einem Worst Case von ${\mathcal {O}}(n^{2})$.
Wie bei Quicksort ist die Schnellauswahl im Allgemeinen als In-Place-Algorithmus implementiert, und über die Auswahl des k'ten Elements hinaus sortiert sie die Daten teilweise auch.

## Prinzip

In Quicksort gibt es eine Unterprozedur namens partition, die in linearer Zeit eine Liste (von links nach rechts) in zwei Teile gruppieren kann: diejenigen, die kleiner als ein bestimmtes Element sind, und solche, die größer als oder gleich dem Element sind. Hier ist Pseudocode, der eine Partition über die Elementliste[pivotIndex] ausführt:
Dies ist bekannt als das Lomuto-Partitionsschema, das einfacher, aber weniger effizient ist als das ursprüngliche Partitionsschema von Hoare.
In Quicksort sortieren wir beide Zweige rekursiv, was zu einer optimalen ${\mathcal {O}}(n\log n)$ Zeit führt. Bei der Auswahl wissen wir jedoch bereits, in welcher Partition sich unser gewünschtes Element befindet, da sich der Pivot in seiner endgültigen sortierten Position befindet, mit allen, die ihm in einer unsortierten Reihenfolge vorausgehen und allen, die ihm in einer unsortierten Reihenfolge folgen. Daher findet ein einziger rekursiver Aufruf das gewünschte Element in der richtigen Partition, und darauf aufbauend, entsteht der Quickselect-Algorithmus:
Beachten Sie die Ähnlichkeit mit Quicksort: So wie der minimal-basierte Selectionsort ein Teilselectionsort ist, so ist dies eine Teilquicksort, bei der nur ${\mathcal {O}}(\log(n))$ seiner ${\mathcal {O}}(n)$ -Partitionen erzeugt und partitioniert wird. Dieses einfache Verfahren hat eine erwartete lineare Laufzeit und, wie Quicksort, in der Praxis eine recht gute Leistung. Es ist auch ein In-Place-Algorithmus, der nur konstanten Speicher-Overhead erfordert, wenn die Endrekursionsoptimierung verfügbar ist, oder wenn die Endrekursion mit einer Schleife eliminiert wird:

## Zeitkomplexität

Wie Quicksort hat auch der Quickselect eine gute durchschnittliche Leistung, ist aber empfindlich gegenüber dem gewählten Pivot. Wenn gute Pivots gewählt werden, d. h. solche, die den Suchsatz konsequent um einen bestimmten Bruchteil verringern, dann nimmt der Suchsatz exponentiell ab und durch Induktion (oder Summierung der geometrischen Reihen) sieht man, dass die Leistung linear ist, da jeder Schritt linear ist und die Gesamtzeit eine konstante Zeit ist (abhängig davon, wie schnell sich der Suchsatz verringert). Wenn jedoch konsequent schlechte Pivots gewählt werden, wie z. B. die Verringerung um jeweils nur ein einziges Element, dann ist die Worst-Case Performance quadratisch: ${\mathcal {O}}(n^{2})$. Dies geschieht z. B. bei der Suche nach dem maximalen Element einer Menge, wobei das erste Element als Pivot verwendet wird und die Daten sortiert werden.