Quickselect
Also known as Hoare's selection algorithm
In computer science, quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and thus is also known as '''Hoare's selection algorithm'''. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations.
Key facts
- Algorithm.name
- Quickselect
- Algorithm.class
- Selection algorithm
- Algorithm.image
- Animated visualization of the quickselect algorithm. Selecting the 22st smallest value.
- Algorithm.caption
- Animated visualization of the quickselect algorithm. Selecting the 22nd smallest value.
- Algorithm.data
- Array
- Algorithm.best time
- O(n)
- Algorithm.average time
- O(n)
- Algorithm.time
- O(n2)
- Algorithm.space
- O(1)
via Wikipedia infobox
Wikidata facts
- Image
- Selecting quickselect frames.gif
via Wikidata · CC0
Article · Deutsch
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 auf , mit einem Worst Case von . 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.
Abstract from DBpedia / Wikipedia · CC BY-SA