Wikipedia · einfach zusammengefasst · Stand
Quickselect
Es bezieht sich auf den Quicksort-Sortieralgorithmus. Wie Quicksort wurde es von Tony Hoare entwickelt und ist daher auch als Hoare-Auswahlalgorithmus bekannt.
Inhalt5 Abschnitte
Kernidee
Quickselect ist ein Auswahlalgorithmus aus der Informatik. Er findet in einer ungeordneten Liste das k-kleinste Element und kann außerdem die Menge aller Elemente bestimmen, die kleiner gleich diesem k-kleinsten Element sind. Der Algorithmus ist mit Quicksort verwandt und wurde wie Quicksort von Tony Hoare entwickelt; deshalb heißt er auch Hoare-Auswahlalgorithmus.
Quickselect ist wichtig, weil er in der Praxis sehr effizient ist und im Durchschnitt eine lineare Laufzeit hat. Er wird deshalb häufig in effizienten Implementierungen von Selektionsalgorithmen verwendet. Wie Quicksort kann Quickselect im schlechtesten Fall aber sehr langsam werden.
Arbeitsweise
Quickselect nutzt denselben Grundgedanken wie Quicksort: Es wird ein Element als Pivot gewählt. Ein Pivot ist ein Vergleichselement, mit dessen Hilfe die Liste in zwei Bereiche geteilt wird. Danach stehen die kleineren Elemente auf einer Seite und die größeren beziehungsweise gleich großen Elemente auf der anderen Seite.
Der entscheidende Unterschied zu Quicksort ist: Quicksort bearbeitet beide Seiten rekursiv weiter, um die ganze Liste zu sortieren. Quickselect bearbeitet nur die Seite weiter, in der das gesuchte k-kleinste Element liegen muss. Dadurch muss nicht die gesamte Liste sortiert werden.
Partitionieren
Die zentrale Unterprozedur heißt partition. Sie gruppiert eine Liste in linearer Zeit von links nach rechts um ein Pivotelement. Im beschriebenen Lomuto-Partitionsschema wird zuerst der Pivotwert gespeichert und das Pivotelement ans Ende verschoben. Dann läuft ein Index durch den betrachteten Listenbereich. Alle Elemente, die kleiner als der Pivotwert sind, werden nach vorne getauscht. Am Ende wird der Pivot an seine endgültige Position gebracht.
Nach der Partition steht der Pivot genau an der Stelle, an der er auch in der vollständig sortierten Liste stehen würde. Links davon befinden sich kleinere Elemente, rechts davon größere oder gleich große Elemente. Diese beiden Seiten sind dabei noch nicht vollständig sortiert. Das Lomuto-Partitionsschema wird als einfacher, aber weniger effizient als das ursprüngliche Partitionsschema von Hoare beschrieben.
Rekursiver Ablauf
Der Algorithmus erhält eine Liste, linke und rechte Grenzen des aktuell betrachteten Bereichs sowie den Index k des gesuchten Elements. Wenn der Bereich nur noch ein Element enthält, wird dieses Element zurückgegeben. Sonst wird ein Pivotindex zwischen links und rechts gewählt, zum Beispiel zufällig mit einer Formel wie links + floor(rand() % (rechts - links + 1)). Danach wird partition ausgeführt.
Liegt der Pivot nach der Partition genau bei k, ist Liste[k] das gesuchte k-kleinste Element. Liegt k links vom Pivot, wird nur der linke Teil weiter durchsucht. Liegt k rechts vom Pivot, wird nur der rechte Teil weiter durchsucht. Der Wert k muss dabei nicht in jeder Runde verändert werden, weil die Liste ihre Größe behält und nur der betrachtete Suchbereich eingegrenzt wird.
Quickselect ist im Allgemeinen ein In-Place-Algorithmus. Das bedeutet, dass die Daten direkt im vorhandenen Speicherfeld umgeordnet werden, statt eine zusätzliche vollständige Datenstruktur anzulegen. Wenn Endrekursionsoptimierung verfügbar ist oder die Endrekursion durch eine Schleife ersetzt wird, benötigt der Algorithmus nur konstanten zusätzlichen Speicher.
Laufzeit
Die durchschnittliche Laufzeit von Quickselect ist gut und beträgt erwartet O(n). Das liegt daran, dass bei geeigneten Pivots der Suchbereich in jedem Schritt um einen festen Anteil kleiner wird. Dann nimmt der Suchsatz exponentiell ab, und die Summe der linearen Arbeitsschritte ergibt insgesamt lineare Zeit.
Im Vergleich dazu braucht Quicksort im Durchschnitt O(n log n), weil es beide Teilbereiche weiter sortiert. Quickselect reduziert diese Arbeit, weil es nur den Teilbereich weiterverfolgt, in dem das gesuchte Element liegt. In der Beschreibung wird dies als Teilquicksort verglichen, bei dem nur O(log(n)) seiner O(n)-Partitionen erzeugt und partitioniert wird.
Die Worst-Case-Laufzeit von Quickselect ist O(n²). Dieser schlechteste Fall tritt ein, wenn immer schlechte Pivots gewählt werden, die den Suchbereich nur um ein einziges Element verkleinern. Als Beispiel wird die Suche nach dem maximalen Element einer Menge genannt, wenn immer das erste Element als Pivot verwendet wird und die Daten bereits sortiert sind.