Quickselect

Quickselect

Visualisation animée de l'algorithme de sélection rapide. Sélection de la 22ème plus petite valeur.

Découvreur ou inventeur	Charles Antony Richard Hoare
Date de découverte	1961
Problème lié	Algorithme de sélection
Structure des données	Tableau
À l'origine de	Médiane des médianes

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)$

En algorithmique, quickselect est un algorithme de sélection qui retourne le k^e 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 k^e é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:

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

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²). 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.