Quickselect
From Wikipedia, the free encyclopedia
| Découvreur ou inventeur | |
|---|---|
| Date de découverte | |
| Problème lié | |
| Structure des données | |
| À l'origine de |
| Pire cas | |
|---|---|
| Moyenne | |
| Meilleur cas |
| Pire cas |
|---|
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[1].
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.
Quicksort utilise une fonction auxiliaire, appelée partition, qui réorganise la liste allant de la position gauche à la position droite en deux parties : les éléments qui sont plus petits qu'un certain élément appelé pivot, et ceux qui sont supérieurs ou égaux au même élément. Voici le pseudo-code qui crée cette partition:
fonction partition(list, gauche, droite, pivot)
ValeurPivot := list[pivot]
échanger list[pivot] et list[droite] // Déplace le pivot à la fin
IndiceStockage := gauche
pour i de gauche à droite-1
si list[i] < ValeurPivot
échanger list[IndiceStockage] et list[i]
incrémenter IndiceStockage
échanger list[droite] et list[IndiceStockage] // Met le pivot à sa place définitive.
retourner IndiceStockage
Quicksort trie récursivement les deux branches, créant un pire cas en temps de Ω(n log n). Cependant la sélection choisit de quel côté de la partition se trouve l'élément, puisque le pivot est à sa place finale, avec les éléments plus petits à gauche et les plus grands à droite. Donc un seul appel récursif suffit à créer l'algorithme quickselect:
// Retourne le n-ième plus petit élément de la liste entre gauche et droite incluse (i.e. gauche ≤ n ≤ droite).
// La taille de la liste reste la même à chaque appel récursif, donc n n'a pas besoin d'être changé.
fonction select(list, gauche, droite, n)
si gauche = droite // S'il n'y a qu'un élément
retourner list[gauche] // Retourne cet élément
pivot := ... // Choisit un pivot entre gauche et droite, par exemple
// gauche + Math.floor(Math.random() * (droite - gauche + 1))
pivot := partition(list, gauche, droite, pivot)
// Si le pivot est à sa position finale
si n = pivot
retourner list[n]
sinon si n < pivot
retourner select(list, gauche, pivot - 1, n)
sinon
retourner select(list, pivot + 1, droite, n)
Remarquons la ressemblance avec quicksort: tout comme l'algorithme basé sur la sélection de l'élément minimal est un algorithme de tri partiel, quickselect est un quicksort partiel, créant et partitionnant uniquement O(log n) de ces O(n) partitions. Cette procédure a en moyenne un temps d'exécution linéaire, et de bonnes performances en pratique. C'est en plus un algorithme en place, utilisant un espace constant supplémentaire puisque la récursion terminale peut être éliminée avec une boucle telle que:
fonction select(list, gauche, droite, n)
boucle
si gauche = droite
retourner list[gauche]
pivot := ... // Choix du pivot entre gauche et droite
pivot := partition(list, gauche, droite, pivot)
si n = pivot
retourner list[n]
sinon si n < pivot
droite := pivot - 1
sinon
gauche := pivot + 1
