- Partie en cours de partition
- Pivot
- Comparées
- Échangées
- En place
Quicksort
Le quicksort, ou tri rapide, choisit un pivot, place toutes les valeurs plus petites avant lui et toutes les autres après, puis trie les deux côtés de la même façon. Après chaque partition, le pivot est à sa place définitive. Choisissez la règle du pivot, lancez le tri à la vitesse voulue ou avancez d'une comparaison à la fois, et voyez pourquoi un mauvais pivot sur une liste triée rend le quicksort lent. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. Les tuiles comptent les comparaisons, les échanges et les partitions. Choisissez le nombre de barres, leur ordre de départ et le choix du pivot, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Choisissez le nombre de barres et leur ordre de départ : aléatoire, presque trié, inversé ou avec peu de valeurs distinctes. Ou saisissez vos propres nombres.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
- Choisissez la règle du pivot : la dernière valeur, la valeur du milieu, une valeur aléatoire ou la médiane de trois. Essayez chacune sur une liste triée.
Comment fonctionne le quicksort
Choisissez une valeur de la partie à trier comme pivot et placez-la à la fin. Parcourez les autres valeurs de gauche à droite ; chaque valeur plus petite que le pivot est échangée vers une partie gauche qui grandit depuis le début. Échangez ensuite le pivot juste après la partie gauche. Tout ce qui est avant lui est maintenant plus petit et rien de ce qui est après ne l'est, donc le pivot est à sa place définitive. Triez de la même façon la partie avant et la partie après, jusqu'à ce que chaque partie ne contienne qu'une valeur.
Pourquoi le pivot compte
Quand le pivot tombe près du milieu, chaque partition divise le problème par deux, et les comparaisons croissent comme n log n : environ 190 pour 40 valeurs aléatoires. Quand le pivot est la plus petite ou la plus grande valeur, un côté est vide et l'autre contient tout le reste. Avec la dernière valeur comme pivot, cela arrive à chaque étape sur une liste triée ou inversée, et le tri demande n(n − 1)/2 comparaisons, soit 780 pour 40 valeurs. Un pivot aléatoire ou la médiane de la première valeur, de celle du milieu et de la dernière évite cela en pratique.
Questions fréquemment posées
Comment fonctionne le quicksort ?
Il choisit un pivot, partitionne la liste pour que les valeurs plus petites viennent avant le pivot et les autres après, puis trie les deux côtés par quicksort. Après chaque partition, le pivot est à sa place définitive.
Pourquoi le quicksort est-il lent sur une liste triée ?
Avec la première ou la dernière valeur comme pivot, une liste triée donne toujours la plus petite ou la plus grande valeur comme pivot. Un côté de la partition est alors vide, chaque partition n'enlève donc qu'une valeur, et le tri demande n(n − 1)/2 comparaisons. Un pivot aléatoire ou la médiane de trois règle ce problème en pratique.
Le quicksort est-il plus rapide que le tri fusion ?
Souvent, en pratique : il trie en place, n'a besoin d'aucun tampon, et sa boucle interne est très simple. En moyenne, il fait un peu plus de comparaisons que le tri fusion, et son pire cas est n², alors que le tri fusion est toujours en n log n. Les tris des bibliothèques comme l'introsort commencent par un quicksort et passent au tri par tas si les découpages deviennent trop inégaux.
Le quicksort est-il stable ?
Non. Une partition échange des valeurs sur de longues distances, donc des valeurs égales peuvent changer d'ordre.
Mes nombres sont-ils envoyés quelque part ?
Non. Le tri s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur