# Quickselect

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 $O(n)$. Quickselect et ses variantes sont des algorithmes souvent utilisés dans le monde réel.

## Algorithme

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:
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:
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:

## Complexité en temps

Tout comme quicksort, l'efficacité de l'algorithme quickselect dépend du choix du pivot. Si le choix de pivot permet de faire décroître la taille du tableau à chaque étape d'une même fraction, alors la décroissance est exponentielle, et la complexité en temps est linéaire, comme une série géométrique. Si au contraire le pivot ne fait diminuer la taille que de 1, alors le pire cas a une complexité quadratique, O(n$^2$). Cela arrive principalement si le pivot est l'élément le plus à droite et que le tableau est déjà trié.

## Variantes

La solution la plus simple est de choisir un pivot aléatoire, qui donne avec grande probabilité un temps d'exécution linéaire. Comme algorithme déterministe, la stratégie de la médiane de 3 valeurs, comme dans quicksort, donne un temps d'exécution linéaire sur les données partiellement triées, ce qui arrive souvent en vrai. Mais la complexité pire-cas peut toujours être atteinte, David Musser a montré comment atteindre ce pire cas, contre lequel il existe son algorithme introselect.
Une complexité linéaire en pire-cas peut-être obtenue via la méthode de médiane des médianes, avec un surcout pratique considérable, ce qui fait qu'il n'est pas utilisé en pratique. Il est possible de le combiner avec le quickselect basique, et cet algorithme pour le pire cas, afin d'avoir de bons résultats en pratiques et une bonne complexité dans le pire cas, c'est ce que fait introselect.
Plus précisément, la complexité moyenne en temps est $n(2+2\log 2+o(1))\leq 3.4n+o(n)$ pour un pivot aléatoire (dans le cas de la recherche de la médiane, d'autres k sont plus rapides). La constante peut être descendue à 3/2 avec un pivot plus complexe, utilisant l'algorithme de Floyd–Rivest, dont la complexité moyenne en temps est de $1.5n+O(n^{1/2})$ pour le calcul de la médiane, et plus rapide avec d'autres k.