Quicksort
Le quicksort, ou tri rapide, est l'un des algorithmes de tri les plus utilisés. Il choisit un pivot, sépare la liste entre les valeurs plus petites que le pivot et les autres, puis trie les deux côtés de la même façon. Il est rapide en pratique et n'a pas besoin de liste supplémentaire, mais sa vitesse dépend du pivot.
L'idée
Choisissez une valeur comme pivot. Réorganisez la liste pour que chaque valeur plus petite que le pivot vienne avant lui et toutes les autres après. Cette réorganisation s'appelle une partition, et elle laisse le pivot exactement là où il doit être dans la liste triée. Les deux côtés sont maintenant des problèmes indépendants : triez chacun par quicksort. Un côté d'une seule valeur, ou vide, est déjà trié.
La partition, étape par étape
L'application utilise la partition de Lomuto. Le pivot est placé à la fin de la partie. Un repère part du début : tout ce qui est avant lui est plus petit que le pivot. Chaque autre valeur est comparée au pivot ; si elle est plus petite, elle est échangée à la position du repère et le repère avance d'une place. À la fin, le pivot est échangé à la position du repère. Prenons 5, 1, 4, 2, 8 avec la dernière valeur comme pivot : les quatre valeurs sont plus petites que 8, donc 8 reste à la fin. La partie 5, 1, 4, 2 est partitionnée autour de 2, ce qui donne 1, 2, 4, 5, puis 4, 5 autour de 5. Cela fait 8 comparaisons, 2 échanges et 3 partitions.
Bons et mauvais pivots
Si chaque pivot tombait au milieu, chaque partition diviserait le problème par deux, et le tri demanderait environ n log₂ n comparaisons. Sur une liste aléatoire, les pivots sont rarement parfaits mais généralement assez bons : pour 40 valeurs aléatoires, l'application compte environ 190 comparaisons. Le pire cas survient quand le pivot est toujours la plus petite ou la plus grande valeur. Avec la dernière valeur comme pivot, une liste déjà triée, ou inversée, fait exactement cela : chaque partition n'enlève que le pivot, et le tri demande n(n − 1)/2 comparaisons, soit 780 pour 40 valeurs.
Choisir le pivot
Un pivot aléatoire rend le pire cas extrêmement improbable pour n'importe quelle entrée, car aucun ordre particulier ne peut le piéger. La médiane de trois, la valeur médiane du premier élément, de celui du milieu et du dernier, est peu coûteuse et gère bien les listes triées et inversées. Essayez les deux sur une liste triée dans l'application : les comparaisons passent de 780 à environ 150. Beaucoup de valeurs égales posent un autre problème : elles tombent toutes du même côté du pivot. Une partition en trois, qui garde les valeurs égales au pivot dans une partie centrale, règle ce problème.
Histoire et usage
Tony Hoare a inventé le quicksort en 1959 et l'a publié en 1961. Sa propre partition parcourt la liste depuis les deux bouts et fait moins d'échanges ; la version plus simple de Lomuto, montrée ici, s'est répandue grâce aux manuels. Le quicksort trie en place et sa boucle interne est très courte, il est donc généralement plus rapide que le tri fusion en pratique, mais il n'est pas stable. L'introsort, le tri de la bibliothèque standard C++, lance un quicksort et passe au tri par tas si les partitions deviennent trop inégales, si bien que son pire cas reste n log n.
À vous d'essayer
Ouvrez l'application et appuyez sur Étape. La partie en cours de partition est ombrée, le pivot a sa propre couleur, et la ligne pointillée marque la fin de la partie gauche, celle des valeurs plus petites que le pivot. Chaque pivot devient vert quand il atteint sa place définitive. Choisissez une liste triée et la dernière valeur comme pivot, passez ensuite à la médiane de trois, et comparez les compteurs.
Questions fréquemment posées
Quelle est la complexité en temps du quicksort ?
O(n log n) en moyenne et avec de bons pivots, O(n²) dans le pire cas. Il trie en place ; la récursion demande O(log n) de mémoire supplémentaire si le plus petit côté est trié en premier.
Quelle est la différence entre les partitions de Lomuto et de Hoare ?
Lomuto garde un seul repère et parcourt la liste de gauche à droite : c'est facile à suivre, et c'est ce que montre cette application. Hoare parcourt la liste depuis les deux bouts l'un vers l'autre et échange les paires qui sont du mauvais côté, ce qui fait en moyenne environ trois fois moins d'échanges.
Pourquoi le quicksort est-il lent quand beaucoup de valeurs sont égales ?
Les valeurs égales au pivot vont toutes du même côté, donc une liste avec peu de valeurs distinctes se coupe de façon inégale, et une liste de valeurs égales est aussi mauvaise que le pire cas. Une partition en trois, qui regroupe au milieu les valeurs égales au pivot, évite cela.
Le quicksort est-il stable ?
Non. Les échanges pendant une partition déplacent des valeurs sur de longues distances, donc des valeurs égales peuvent changer d'ordre.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le quicksort