Le tri rapide est une méthode de tri récursive fondée sur le principe «diviser-pour-résoudre». Il procède à un partitionnement de la liste à trier à partir d'une valeur pivot et à un tri indépendant des deux sous-listes obtenues. Bien qu'il existe différentes manières de choisir le pivot, nous opterons, dans cette présentation, toujours pour le premier élément de la liste. A chaque itération, l'algorithme consiste à placer la valeur pivot à sa position définitive de telle sorte que tous les éléments situés à sa gauche lui soient inférieurs ou égaux et tous les éléments situés à sa droite lui soient supérieurs ou égaux. A la fin de chaque itération, la position de la valeur pivot permet de scinder la liste
initiale en deux sous-listes sur lesquelles le processus se répète récursivement jusqu'à obtenir des sous-listes de longueur inférieure ou égale à 1.
Le but de ce paragraphe est d'analyser le déroulement du tri rapide en étudiant directement le code Python de son implémentation:
Implémentation en Python du tri rapide
Comme nous pouvons le constater, l'implémentation du tri rapide est récursive au vu de l'utilisation de la fonction Tri_Rapide_Partition qui est appliquée successivement à chaque sous-liste créée par la fonction partition.
A vous de jouer !
En vous basant sur le code Python du tri rapide (téléchargeable ici), répondez à chacun des points suivants:
Décrivez chacune des étapes du partitionnement réalisé par le tri rapide lors du premier appel à la fonction Tri_Rapide_Partition sur la liste [54, 26, 93, 31, 77, 17, 44, 55, 20, 31]. Décrivez le rôle des pointeurs gauche et droite dans le processus de partitionnement entrepris par la fonction partition puis résumez le but visé par ce premier partitionnement.
Décrivez les résultats intermédiaires produits par chaque appel de la fonction Tri_Rapide_Partition lors du tri rapide de la liste [54, 26, 93, 31, 77, 17, 44, 55, 20, 31].
Déterminez le nombre de comparaisons nécessaires au tri rapide d'une liste comportant n éléments tout d'abord si le partitionnement se fait toujours au milieu de la liste (meilleur des cas) puis si le partitionnement se fait toujours à l'extrémité gauche de la liste (pire des cas).
Solution
Une fois le pivot 54 choisi, le partitionnement est rendu possible grâce à deux pointeurs gauche et droite placés initialement au début et à la fin de la liste (aux positions 1 et 9). Le but de l'appel à la fonction partition est de déplacer les éléments situés du mauvais côté de 54 tout en déterminant la position définitive de 54. A ce dessein, la fonction commence par incrémenter le pointeur gauche jusqu'à atteindre une valeur supérieure à 54. Ensuite, elle décrémente le pointeur droite afin d'atteindre une valeur inférieure à 54. A ce moment, la fonction a trouvé deux valeurs, à savoir 31 et 93, qui ne sont pas situées correctement relativement au pivot 54 et échange par conséquent
leur place respective. Ce procédé se répète jusqu'à ce que le pointeur gauche atteigne une position supérieure à celle du pointeur droite comme l'illustre la figure suivante:
Premier partitionnement de la liste [54, 26, 93, 31, 77, 17, 44, 55, 20, 31]
A ce moment, le déplacement des pointeurs gauche et droite se termine et la position du pointeur droite correspond au point de scission. La valeur du pivot peut être échangée avec celle située au point de scission (en l'occurrence 44) ce qui la place à sa position définitive. En effet, tous les éléments situés à sa gauche lui sont alors inférieurs et tous ceux situés à sa droite lui sont supérieurs. La liste peut alors être scindée en deux sous-listes sur lesquelles le processus se fera de manière analogue.
En procédant récursivement sur chacune des 2 sous-listes formées par la première étape de l'algorithme décrite ci-dessus, nous obtenons le déroulement suivant du tri rapide:
Déroulement du tri rapide sur la liste [54, 26, 93, 31, 77, 17, 44, 55, 20, 31]
Comme le premier appel récursif se fait toujours sur la sous-liste située à gauche de la position définitive du pivot, l'algorithme trie, à chaque étape, la liste de gauche à droite.
En résumé, le tri rapide procède de la manière suivante:
Mise en application du tri rapide sur une liste d'entiers
La meilleure situation qui puisse arriver pendant l'exécution du tri rapide d'une liste de n éléments est que chaque étape du partitionnement divise la liste exactement en son centre. Dans ce cas, le nombre de comparaisons nécessaires est la somme de n (couvrant l'examen de chaque élément par les pointeurs gauche et droite) avec le nombre de comparaisons nécessaires au tri de chacune des sous-listes formées par le partitionnement. En d'autres termes, le nombre de comparaisons nécessaires vérifie les équations suivantes:
Calcul du nombre de comparaisons nécessaires dans le meilleurs des cas
Dans le pire des cas, lorsque la liste est déjà triée, le point de scission est à chaque fois placé à l'extrémité gauche ou droite. Dans ce cas, la division n'est qu'apparente et à chaque étape, le nombre de comparaisons ne diminue que de 1 par rapport au nombre de comparaisons nécessaires à l'étape précédente. Par conséquent, dans ce cas, le tri rapide nécessite un nombre de comparaisons de l'ordre de n². Afin d'éviter ce cas extrême, il est possible d'améliorer l'algorithme de tri rapide en choisissant à chaque étape un pivot permettant de partager la liste plus ou moins en son centre et bénéficier ainsi d'une vitesse de calcul supérieure.
|
Notons finalement qu'il est possible de choisir les pivots de telle sorte qu'en moyenne ils partagent à chaque itération la liste en deux parties égales. Il est alors possible de montrer qu'en moyenne, le nombre de comparaisons nécessaires au tri rapide est de l'ordre de 2nlog(n), ce qui s'avère très performant par rapport aux algorithmes de tri élémentaires étudiés en début de chapitre. Ce constat peut être vérifié expérimentalement en recourant au programme ci-joint permettant de calculer le temps nécessaires à chacun des algorithmes pour trier une liste d'entiers.
Terminons cette section en opposant le tri par bulles et le tri rapide dans l'ordonnancement d'une série de boules et en montrant que le vainqueur de ce duel fictif est bel et bien le deuxième algorithme:
Comparaison des performances du tri par bulles et du tri rapide
Algorithmes et structures de données
