QuickSort.

Dans la méthode de Batcher, l'ordre dans lequel les comparaisons doivent être effectuées est prédéterminé et ceci ne permet évidemment pas de tenir compte des particularités des données. En 1962, C.A.R.Hoare publia une méthode qu'il appela "quicksort" et qui permet de placer un élément à sa place et ramenant ainsi le problème au tri des 2 morceaux de tableau entourant cet élément.

En voici une description, avec une partitionnement dû à R.Sedgewick. Nous l'appliquerons à un tableau A de N éléments numérotés de 1 à N:
considérons 2 pointeurs i et j qui ont comme valeurs initiales respectives 2 et N.
Recherchons, en augmentant i, le premier élément supérieur à A1 (il marque la limite des nombres inférieurs à A1) et, en diminuant j, le premier élément inférieur à A1 (qu'il faudra placer dans le morceau de tableau des nombres inférieurs à A1) Si i<j il faut échanger Aiet Aj Il faut ensuite continuer des traitements identiques jusqu'au moment où i>=j On termine par l'échange éventuel de Aj et A1.

Exemple: il faut trier

1 2 3 4 5 6 7 8
7 8 9 1 0 2 5 6

Recherchons, à partir de A2 et en nous déplaçant vers la droite, le premier élément supérieur à A1. Il s'agit de A2 qui vaut 8 (en rouge).
De même, cherchons à partir de A8 et en nous déplaçant vers la gauche, le premier élément inférieur à A1. Il s'agit de A8 qui vaut 6 (en magenta).
1 2 3 4 5 6 7 8
7 8 9 1 0 2 5 6

On les échange
1 2 3 4 5 6 7 8
7 6 9 1 0 2 5 8

On continue à chercher, en nous déplaçant vers la droite, le premier élément supérieur à A1 mais à partir de A3. Il s'agit de A3 qui vaut 9. De même, cherchons à partir de A7 et en nous déplaçant vers la gauche, le premier élément inférieur à A1. Il s'agit de A7 qui vaut 5.
1 2 3 4 5 6 7 8
7 6 9 1 0 2 5 8

On les échange.
1 2 3 4 5 6 7 8
7 6 5 1 0 2 9 8

On continue à chercher, en nous déplaçant vers la droite, le premier élément supérieur à A1 mais à partir de A4. Il n'y en a pas et i vaut donc 8. De même, cherchons à partir de A6 et en nous déplaçant vers la gauche, le premier élément inférieur à A1. Il s'agit de A6 qui vaut 5 et j vaut 6. Comme i>j, il n'y a pas d'échange mais par contre, on échange A1 et Aj
1 2 3 4 5 6 7 8
2 6 5 1 0 7 9 8

Et l'élément en position 6 est à sa place définitive. Il reste à trier les morceaux de tableau dont les numéros vont de 1 à 5 et de 7 à 8. Commençons par la partie de gauche. Recherchons, à partir de A2 et en nous déplaçant vers la droite, le premier élément supérieur à A1. Il s'agit de A3 qui vaut 6 (en rouge). De même, cherchons à partir de A5 et en nous déplaçant vers la gauche, le premier élément inférieur à A1. Il s'agit de A5 qui vaut 0 (en magenta).
1 2 3 4 5 6 7 8
2 6 5 1 0 7 9 8

On les échange.
1 2 3 4 5 6 7 8
2 0 5 1 6 7 9 8

On continue à chercher, en nous déplaçant vers la droite, le premier élément supérieur à A1 mais à partir de A3. Il s'agit de A3 qui vaut 5. De même, cherchons à partir de A4 et en nous déplaçant vers la gauche, le premier élément inférieur à A1. Il s'agit de A4 qui vaut 1.
1 2 3 4 5 6 7 8
2 0 5 1 6 7 9 8

On les échange.
1 2 3 4 5 6 7 8
2 0 1 5 6 7 9 8

On continue à chercher, en nous déplaçant vers la droite, le premier élément supérieur à A1 mais à partir de A4. Il s'agit de A4 qui vaut 5 et i égale 4. De même, cherchons à partir de A3 et en nous déplaçant vers la gauche, le premier élément inférieur à A1. Il s'agit de A3 qui vaut 1 et j vaut 3. Comme i>j, il n'y a pas d'échange mais par contre, on échange A1 et Aj
1 2 3 4 5 6 7 8
1 0 2 5 6 7 9 8

Et l'élément en position 3 est à sa place définitive. Il reste à trier les morceaux de tableau dont les numéros vont de 1 à 2, de 4 à 5. N'oublions pas la partie de 7 à 8. Commençons par la partie de gauche. Recherchons, é partir de A2 et en nous déplaçant vers la droite, le premier élément supérieur à A1. Il n'y en a pas et i=2. De même, cherchons à partir de A2 et en nous déplaçant vers la gauche, le premier élément inférieur à A1. Il s'agit de A2 qui vaut 0. Comme i>=j, il n'y a pas d'échange entre Aiet Aj mais bien entre A1 et Aj.
1 2 3 4 5 6 7 8
0 1 2 5 6 7 9 8

Occupons nous de la partie du tableau dont les indices vont de 4 à 5. Recherchons, é partir de A5 et en nous déplaçant vers la droite, le premier élément supérieur à A4. Il s'agit de A5 et i=5. De même, cherchons à partir de A5 et en nous déplaçant vers la gauche, le premier élément inférieur à A4. Il n'y en a pas et j vaut 4. Comme i>=j, il n'y a pas d'échange entre Aiet Aj mais bien entre A4 et Aj. Comme il s'agit du même élément, cette partie est aussi triée.
1 2 3 4 5 6 7 8
0 1 2 5 6 7 9 8

Occupons nous maintenant de la partie du tableau dont les indices vont de 7 à 8. Recherchons, à partir de A8 et en nous déplaçant vers la droite, le premier élément supérieur à A7. Il n'y en a pas et i=8. De même, cherchons à partir de A8 et en nous déplaçant vers la gauche, le premier élément inférieur à A7. Il s'agit de A8 et j vaut 8. Comme i>=j, il n'y a pas d'échange entre Aiet Aj mais bien entre A7 et Aj.
1 2 3 4 5 6 7 8
0 1 2 5 6 7 8 9

Et le tri est terminé. 

tableau Ti i=1,…,100 de entier
entier i, N

procédure Trie(bT, ¯Inf, ¯Sup)
  paramètre T: tableau de entier
            Inf,Sup: entier
entier: Tmp, i, j

si Inf³ Sup alors
sinon i ß Inf+1
      j ß Sup
      tant que NOT (i³j) faire
        tant que NOT ((Ti>TInf) ou (i=j)) faire
          i ß i+1
        ftant
        tant que NOT ((Tj<TInf) ou (j=i-1)) faire
          j ß j-1
        ftant
        si i<j alors Tmp ß Ti
                     Ti ß Tj
                     Tj ß Tmp
        fsi
      ftant
      si Tj<TInf alors	Tmp ß TInf
                       TInf ß Tj
                       Tj ß Tmp
      fsi
      Trie(T,Inf,j-1)
      Trie(T,j+1,Sup)
fsi
fproc

N ß RANDOM(101)
pour i de 1 à N faire
  Ti ß RANDOM(101)
fpour
Trie(T,1,N)
Cliquez ici pour charger une archive avec une implémentation du quicksort en Delphi.
Note: le code du tri est identique pour le Turbo Pascal.
Page précédente.
Page d'accueil.