Quick Sort / Tri Rapide

1. Principe

Le Quick Sort est assez simple à comprendre, mais assez compliqué à transcrire en algorithme. Le Quick Sort consiste à trier un tableau en le découpant récursivement en 2 sous tableaux, où les éléments du premier tableau sont inférieurs aux éléments du second. En faisant une opération récursive, on découpe le tableau en élément de plus en plus petit, jusqu'à arriver à un sous tableau à un seul élément, qui est donc forcément trié. Ensuite, en remontant, les éléments sont triés petit à petit.

2. Algorithme

2. 1. Codage

L'algorithme se découpe en 2 fonctions : une fonction SPLIT qui s'occupe de réarranger le tableau, et une fonction QUICKSORT qui gère la récursivité et le découpage en sous tableaux.

    Procédure SPLIT (Element : Tableau; K, L, I: Entier) 

      I <- K 

      J <- L+1 

      X <- Element (I) 

      REPETER 

        REPETER 

          J <- J-1 

        JUSQU'A (Element (J) < X) ou (I = J) 

        Element (I) <- Element (J) 

        TANT QUE (I < J) et (Element (I) <= X) FAIRE 

          I <- I+1 

        FIN TANT QUE 

        Element (J) <- Element (I) 

      JUSQU'A I = J 

      Element (I) <- X 

    Fin Procédure 

    Procédure QUICKSORT (Element: Tableau; K, L: Entier) 

      SI K < L ALORS 

        SPLIT (Element , K, L, I) 

        QUICKSORT (Element, K, I-1) 

        QUICKSORT (Element, I+1, L) 

      FIN SI 

    Fin Procédure

2. 2. Variables

Nom	Fonction
I	Compteur correspondant à l'indice du pivot (indice de l'élément qui sépare les sous-tableaux)
J	Compteur courant dans le tableau
K	Premier indice du tableau
L	Dernier indice du tableau
X	Valeur du premier élément du tableau
Element	Tableau (ou liste, pile...) à trier

4. Exemples

4. 1. PHP

    function mysplit(&$TopDest, &$K, &$L, &$I) { 

      $I = $K; 

      $J = $L+1; 

      $X = $TopDest[$I]; 

      do { 

        do { 

          $J = $J-1; 

        } 

        while (($TopDest[$J] > $X) && ($I <> $J)); 

        $TopDest[$I] = $TopDest[$J]; 

        while (($I < $J) && ($TopDest[$I] <= $X)) { 

          $I = $I+1; 

        } 

        $TopDest[$J] = $TopDest[$I]; 

      } 

      while ($I != $J); 

      $TopDest[$I] = $X; 

    } 

    function quicksort (&$TopDest, $K, $L) { 

      if ($K < $L) { 

        mysplit ($TopDest, $K, $L, $I); 

        quicksort ($TopDest, $K, $I-1); 

        quicksort ($TopDest, $I+1, $L); 

      } 

    }

4. 2. ASP / Visual Basic

    Sub split(TopDest(), K, L, I) 

      dim J 

      dim X 

      I = K 

      J = L+1 

      X = TopDest(I) 

      do 

        do 

          J = J-1 

        loop until (TopDest(J) < X) or (I = J) 

        TopDest(I) = TopDest(J) 

        do while (I < J) and (TopDest(I) <= X) 

          I = I+1 

        loop 

        TopDest(J) = TopDest(I) 

      loop until I = J 

      TopDest(I) = X 

    end Sub 

    Sub quicksort (TopDest, K, L) 

      dim I 

      if K < L then 

        split TopDest, K, L, I 

        quicksort TopDest, K, I-1 

        quicksort TopDest, I+1, L 

      end if 

    end Sub

Page modifiée le : 02/05/2022