Le tri à peigne ou tri de Dobosiewicz

Le tri à peigne

Le tri à peigne est un algorithme de tri par comparaison qui améliore de façon notable les performances du tri à bulle. Cet algorithme fut conçu en 1980 par Włodzimierz Dobosiewicz. Quelques années plus tard, en 1991, Stephen Lacey et Richard Box ont montré dans un article dans Byte Magazine que l'idée de Donald Shell pouvait s'appliquer également, et avec autant de bénéfices, au tri bulle.

Le principe est de ne plus comparer uniquement des éléments adjacents, mais de commencer par comparer des éléments plus lointains, puis de raccourcir progressivement l'intervalle entre les éléments pour aboutir finalement à un tri à bulle classique.

L'animation ci-après détaille le fonctionnement de ce tri :

Démonstration du tri à peigne

  1. PROCEDURE tri_peigne ( TABLEAU a[1:n])
  2. gap n
  3. REPETER
  4.     permut FAUX
  5.     gap gap / 1.3
  6.     SI gap < 1 ALORS gap 1
  7.     POUR i VARIANT DE 1 A n AVEC UN PAS gap FAIRE
  8.         SI a[i] > a[i+gap] ALORS
  9.             echanger a[i] et a[i+gap]
  10.             permut VRAI
  11.         FIN SI
  12.     FIN POUR
  13. TANT QUE permut = VRAI OU gap > 1
  1. let tri_peigne tableau =
  2.     let gap = ref (Array.length tableau) and permutation = ref true in
  3.     while (!permutation = true) or (!gap > 1)  do
  4.         permutation := false;
  5.         gap := int_of_float(float_of_int(!gap) /. 1.3);
  6.         if !gap < 1 then gap := 1;
  7.         for en_cours = 0 to (Array.length tableau) - !gap - 1 do
  8.             if tableau.(en_cours) > tableau.(en_cours + !gap) then
  9.             begin
  10.                 (* On echange les deux elements *)
  11.                 permutation := true;
  12.                 let temp = tableau.(en_cours) in
  13.                 begin
  14.                    tableau.(en_cours) <- tableau.(en_cours + !gap);
  15.                    tableau.(en_cours + !gap) <- temp;
  16.                 end
  17.             end
  18.         done;
  19.     done;
  20. tableau;;
  1. type tab = array[1..20] of integer;
  2. procedure tri_peigne(var tableau : tab);
  3. var permutation : boolean;
  4.     en_cours : integer;
  5.     temp : integer;
  6.     gap : integer;
  7.  
  8. begin
  9.     gap:=20;
  10.     REPEAT
  11.         permutation := false;
  12.         gap:=trunc(gap / 1.3);
  13.         if gap<1 then gap := 1;
  14.         for en_cours := 1 to 20 - gap do
  15.         begin
  16.             if (tableau[en_cours] > tableau[en_cours + gap]) then
  17.             begin
  18.                 { on échange les deux éléments }
  19.                 temp := tableau[en_cours];
  20.                 tableau[en_cours]:=tableau[en_cours + gap];
  21.                 tableau[en_cours+gap]:=temp;
  22.                 permutation := true;
  23.             end;
  24.         end;
  25.     UNTIL (not permutation) and (gap = 1);
  26. end;
  1. import math  
  2. def tri_peigne(tableau):
  3.     permutation = True
  4.     gap = len(tableau)
  5.     while (permutation == True) or  (gap>1):
  6.         permutation = False
  7.         gap = math.floor(gap / 1.3)
  8.         if gap<1: gap = 1
  9.         for en_cours in range(0, len(tableau) - gap):
  10.             if tableau[en_cours] > tableau[en_cours + gap]:
  11.                 permutation = True
  12.                 # On echange les deux elements
  13.                 tableau[en_cours], tableau[en_cours + gap] = \
  14.                 tableau[en_cours + gap],tableau[en_cours]
  15.     return tableau  
  1. typedef int bool;
  2. enum { false, true };
  3.  
  4. void tri_peigne(int* tableau)
  5. {
  6.     int gap = 20;
  7.     bool permutation = true;
  8.     int en_cours;
  9.    
  10.     while (( permutation) || (gap>1)) {
  11.         permutation = false;
  12.         gap = gap / 1.3;
  13.         if (gap<1) gap=1;
  14.         for (en_cours=0;en_cours<20-gap;en_cours++) {
  15.             if (tableau[en_cours]>tableau[en_cours+gap]){
  16.                 permutation = true;
  17.                 // on echange les deux elements
  18.                 int temp = tableau[en_cours];
  19.                 tableau[en_cours] = tableau[en_cours+gap];
  20.                 tableau[en_cours+gap] = temp;
  21.             }
  22.         }
  23.     }
  24. }

Le choix du facteur de réduction est primordial pour l'efficacité de cet algorithme. En général, on prend un facteur de réduction compris entre 1.25 et 1.33. L'animation ci-dessus utilise 1.3 comme facteur de réduction.

Cet algorithme n'est pas stable, comme vous pouvez le vérifier ici.


Si on applique cet algorithme au petit jeu de la page précédente, on obtient :



 



Comme pour le tri de Shell la complexité du tri à peigne est très difficile à calculer. On considère généralement que, dans le meilleur des cas, elle est linéaire (en O(n)), et que, dans le pire des cas elle est en Θ(n2). En moyenne elle serait en en O(n log n).

L'application Javascript ci-dessous permet d'évaluer le nombre d'échanges et de comparaisons nécessaires à l'algorithme pour trier une liste. Choisissez le mode de génération de la série à trier, le facteur de réduction, la couleur de la courbe et cliquez sur "calculer". Jusqu'à cinq courbes peuvent être affichées sur le même graphique.

Dans le cas de données générées aléatoirement, l'application effectuera jusqu'à dix passes, pour calculer la moyenne des comparaisons et des déplacements.

Calcul de la complexité du tri à peigne
Réduction :
Taille donnéesGapsPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesGapsPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesGapsPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesGapsPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesGapsPasseNombre comparaisonsNombre échangesTotal
000