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 · Français
En algorithmique, quickselect est un algorithme de sélection qui retourne le ke plus petit élément dans une liste non ordonnée. Comme l'algorithme de tri quicksort, il a été créé par Tony Hoare et il est donc aussi connu comme l' algorithme de sélection de Hoare. Quickselect utilise la même approche que quicksort, choisissant un élément à la fois, afin de partitionner les éléments selon le pivot. Cependant, au lieu de séparer l'ensemble en deux parties comme dans quicksort, l'algorithme quickselect n'utilise la récursion que sur un côté - le côté contenant l'élément qu'il cherche. Cela réduit la complexité en moyenne O(n log n) de quicksort à la complexité en moyenne O(n) de quickselect. Tout comme quicksort, l'algorithme quickselect est en général implémenté en place, et en plus de sélectionner le ke élément, il trie une partie des données. Comme quicksort, il est efficace en pratique avec un temps moyen de . Quickselect et ses variantes sont des algorithmes souvent utilisés dans le monde réel.
Abstract from DBpedia / Wikipedia · CC BY-SA