Tri rapide

Principe

1. Partager le tableau en deux parties (pas nécessairement de même taille) , de façon à  obtenir :
   • Une case dont le contenu constitue la « valeur pivot »
   • En dessous de cette case, on ne doit avoir que des valeurs inférieures ou égales à  la valeur pivot
   • Au-dessus de cette case, on ne doit avoir que des valeurs supérieures à  la valeur pivot
   
   Remarquer que par constuction, la case pivot se trouve à  la bonne place par rapport au résultat final.
2. Effectuer l'opération précédente sur la partie basse du tableau (au-dessous de la case pivot), puis sur la partie haute (au-dessus de la case pivot)
3. Effectuer ainsi des découpes successives jusqu'à   n'avoir que des « morceaux » de 0, 1 ou 2 cases
   Pour trier 0 ou 1 case, il n'y a rien à  faire
   Pour trier 2 cases, il suffit d'effectuer un test (IF ...)

La méthode est donc récursive (on traite chaque « morceau » de la même façon qu'on a traité l'ensemble).
La majeure partie de l'algorithme réside dans la découpe du tableau (et des sous-tableaux)

Une méthode possible :

1. Le contenu de la case n° 1 est pris arbitrairement comme valeur pivot
2. En partant de la case n° 2, et en remontant vers le haut du tableau :
   On compare le contenu de la case sur laquelle on est positionné à  la valeur pivot
   Si ce contenu est supérieur à  la valeur pivot, on l'échange avec celui de la dernière case du tableau
   Si en remontant on trouve une autre valeur supérieure à  la valeur pivot, on l'échange avec l'avant-dernière case du tableau, et ainsi de suite
   On remplit donc la fin du tableau avec des valeurs supérieures à  la valeur pivot
3. Si on a ainsi alimenté les N dernières cases du tableau, on arrête de remonter à  la N-1ème case en partant de la fin
4. On échange alors le contenu de cette case avec celui de la 1ère case du tableau, c'est à  dire la valeur pivot
5. Dans la case où on est positionné se trouve donc la valeur pivot
   Dans les cases situées au-dessus se trouvent toutes les valeurs supérieures à  la valeur pivot
   Dans les cases situées au-dessous se trouvent toutes les valeurs inférieures ou égales à  la valeur pivot
6. On procède de la même façon pour chaque sous-tableau situé de part et d'autre de la case pivot

Algorithme

TriRapide (Tableau, IMin, IMax)

• Si le tableau ne comporte qu'un échelon ou moins
  • Retour
• Si le tableau comporte 2 échelons
  • Si Tableau(IMin) > Tableau(IMax)
    • Echanger (Ttableau (IMax), Tableau( Imin))
    • Retour
• IHaut = IMax
• IPivot = IMin + 1
• Tant que IPivot < Ihaut
  • Si Tableau(IPivot) > Tableau(IMin)
    • Echanger (Tableau(IPivot), Tableau(IHaut))
    • IHaut = IHaut - 1
  • Sinon
    • IPivot = IPivot +1
  • Si Tableau(IPivot) > Tableau(IMin)
    • IPivot = IPivot - 1
• Echanger (Tableau(IMin), Tableau(IPivot))
• TriRapide (Tableau, IMin, IPivot - 1)
• TriRapide (Tableau, IPivot + 1, IMax)

Exemple

Tableau à  trier : [7,5,1,9,2]

1	2	3	4	5
7	5	1	9	2		Valeur pivot=7 : - Case à  alimenter : n° 5
7	5	1	9	2		Comparaison du contenu de la case n° 2 à  la valeur pivot
7	5	1	9	2		Comparaison du contenu de la case n° 3 à  la valeur pivot
7	5	1	9	2		Comparaison du contenu de la case n° 4 à  la valeur pivot
7	5	1	2	9		Echange du contenu des cases n° 4 et 5 ; Case à  alimenter : n° 4 (5-1)
2	5	1	7	9		Puisque Case à  alimenter=Case courante, on s'arrête et on échange les contenus de la case courante et de la case n°1 (pivot)
2	5	1				Tableau bas : valeur pivot=2 - Case à  alimenter : n° 3
2	5	1
2	1	5
1	2	5
1	2	5	7	9		Tous les sous- tableaux restant à  traiter ne comportant qu'une case, le tri est terminé

Exemple de programme en Visual Basic

Remarques

• Lorsqu'on doit programmer l'algorithme de partage du tableau ci-dessus, on utilise généralement une fonction tant que ; la sortie se fait donc avec Bas = Haut, et non Bas < Haut.
  Il faut donc vérifier si le contenu de la case pointée par Bas et inférieur à  la valeur pivot, et si non, décrémenter Bas.
• L'algorithme global est récursif, mais lorsque le tableau est de grande taille et que son partage aboutit à  constituer des « morceaux » de taille très différentes, le nombre d'appels en cascade peut être très important, ce qui conduit à  une saturation de la pile système (on peut faire l'essai avec un tableau de 10.000 nombres initialement trié en inverse).
  Il est donc préférable de remplacer les appels récursifs par une boucle et une pseudo-pile ( tableau contenant les indices min et max des sous-tableaux à  trier).

Variantes

• Dans la découpe du tableau, à  l'étape 3, on effectue systématiquement une inversion entre Haut et Bas lorsque la valeur correspondant à  l'indice Bas est supérieure à  la valeur pivot.
  Cette inversion n'est intéressante que si on remplace le contenu de la case Bas par une valeur inférieure ou égale à  la valeur pivot ; il est donc préférable de décrémenter Haut tant que la case ne contient pas une telle valeur.
  De même, on peut incrémenter Bas sans se poser de question tant que la case pointée contient une valeur inférieure ou égale à  la valeur pivot.
  On gagne ainsi du temps si on a des successions de valeurs inférieures et/ou supérieures à  la valeur pivot.
• Dans l'algorithme global, on effectue des découpes successives en 2 parties jusqu'à   avoir au maximum 2 éléments à  trier (ce qui nécessite de tester le nombre d'éléments du sous-tableau).
  Pour de petits tableaux (entre 10 et 20 éléments), cette méthode n'est pas particulièrement performante ; on peut donc s'arrêter à  une taille de sous-tableau d'une dizaine d'éléments, et effectuer un tri par séléction ou un tri par insertion sur ce sous-tableau.
  En moyenne, il y a généralement un gain de temps

Utilisation

C'est la méthode qui, en moyenne, donne les meilleurs résultats. Elle n'est pas très simple à  programmer, mais permet de nombreuses variantes.

La performance repose sur la méthode de découpe du tableau et la distribution initiale des valeurs, l'idéal étant de pouvoir obtenir des sous-tableaux de taille aussi proche que possible à  chaque étape (ce qu'on ne peut guère prévoir à  priori, en général).

Les performances peuvent être désastreuses (bien plus mauvaises qu'avec n'importe quelle autre méthode) lorsque les sous-tableaux obtenus sont très déséquilibrés (par exemple, un tableau initialement trié en inverse, avec l'algorithme de découpe décrit plus haut).

Retour à  la table des matières des tris

---

Dernière mise à jour de cette page : 12/8/2007