Tri de Shell

Le tri de Shell

Donald L. Shell proposa, en 1959, une variante du tri par insertion. Ce tri consiste à trier séparément des sous-suites de la table, formées par les éléments répartis de h en h. Empiriquement, Shell propose la suite d'incréments vérifiant h1 = 1, hn+1 = 3hn+1 en réalisant les tris du plus grand intervalle possible vers le plus petit.

Dans l'animation ci-dessous - en raison de la faible taille de la table à trier - j'ai choisi h1=1, h2=2, h3=3, h4=4, h5=6. C'est la série proposée par Vaughan Pratt en 1971.

Démonstration du tri de Shell

  1. PROCEDURE tri_Insertion ( Tableau a[1:n],gap,debut)
  2.     POUR i VARIANT DE debut A n AVEC UN PAS gap FAIRE
  3.         INSERER a[i] à sa place dans a[1:i-1];
  4. FIN PROCEDURE;
  5.  
  6. PROCEDURE tri_shell ( Tableau a[1:n])
  7.     POUR gap DANS (6,4,3,2,1) FAIRE
  8.        POUR debut VARIANT DE 0 A gap - 1 FAIRE
  9.           tri_Insertion(Tableau,gap,debut);
  10.        FIN POUR;
  11.     FIN POUR;
  12. FIN PROCEDURE;
  1. let tri_insertion tableau gap debut =
  2.     let i = ref (gap+debut) in
  3.     while (!i < 20) do    
  4.         let en_cours = tableau.(!i) and j = ref (!i - gap) in
  5.             while (!j>=0) && (tableau.(!j)>en_cours) do            
  6.                 tableau.(!j+gap) <-  tableau.(!j);    
  7.                 j := !j - gap;
  8.             done;
  9.             tableau.(!j+gap) <- en_cours;
  10.             i := !i + gap;
  11.     done;;
  12.  
  13. let tri_shell tableau =
  14.     let intervalles = [|6;4;3;2;1|] in
  15.     (* Pour chaque sous-tableau ... *)
  16.     for ngap = 0 to (Array.length intervalles) - 1 do
  17.         let gap = intervalles.(ngap) in
  18.         for debut = 1 to gap do
  19.             (*... on fait un tri par insertion *)
  20.             tri_insertion tableau gap (debut -1);
  21.         done;
  22.     done;
  23. tableau;;
  1. type tab = array[1..20] of integer;
  2. const intervalles : array [1..5] of integer = (6,4,3,2,1);
  3.  
  4. (* Identique à la procedure de tri par insertion classique.
  5. <gap> donne le décalage entre les éléments du sous-tableau
  6. <debut> indique l'index du premier élément du sous-tableau *)
  7. procedure tri_insertion(var tableau : tab; gap : integer; debut : integer) ;
  8.  
  9. var i, j, en_cours : integer;
  10.  
  11. begin
  12.     i := gap + debut;
  13.     while i < 20 do
  14.     begin
  15.         en_cours := tableau[i]; j := i - gap;
  16.         {décalage des éléments du tableau }
  17.         while (j > 0) and (tableau[j] > en_cours) do
  18.         begin
  19.            tableau[j + gap] :=  tableau[j];
  20.            j := j - gap;
  21.         end;
  22.         {on insère l'élément à sa place }
  23.         tableau[j + gap] := en_cours;
  24.         i := i + gap;
  25.     end;
  26. end;
  27.  
  28. procedure tri_shell(var tableau : tab);
  29.  
  30. var i,ngap : integer;
  31.  
  32. begin
  33.     ngap:=1;
  34.     REPEAT
  35.         (* Pour chaque sous-tableau... *)
  36.         for i:=1 to intervalles[ngap] do
  37.         begin
  38.             (*... on fait un tri par insertion *)
  39.             tri_insertion(tableau,intervalles[ngap],i - 1);
  40.         end;
  41.         ngap := ngap + 1;
  42.     UNTIL intervalles[ngap]=1;
  43. end;
  1. def tri_insertion(tableau, gap, debut):
  2.     for i in range(gap + debut,len(tableau),gap):
  3.         en_cours = tableau[i]
  4.         j = i
  5.         #décalage des éléments du tableau }
  6.         while j>0 and tableau[j-gap]>en_cours:
  7.             tableau[j]=tableau[j-gap]
  8.             j = j-gap
  9.         #on insère l'élément à sa place
  10.         tableau[j]=en_cours
  11.  
  12. def tri_shell (tableau):
  13.     for gap in [6,4,3,2,1]:
  14.         # Pour chaque sous-tableau ...
  15.         for debut in range(0,gap):
  16.             #... on fait un tri par insertion
  17.             tri_insertion(tableau,gap,debut)
  1. void tri_insertion(int* t, int gap, int debut)
  2. {
  3.     int j,en_cours;
  4.     for (int i = gap + debut; i < 20; i+=gap) {
  5.         en_cours = t[i];
  6.         for (j = i; j >= gap && t[j - gap] > en_cours; j-=gap) {
  7.             t[j] = t[j - gap];
  8.         }
  9.         t[j] = en_cours;
  10.     }
  11. }
  12.  
  13. void tri_shell(int* t) {
  14.     int intervalles[5]={6,4,3,2,1};
  15.     for (int ngap=0;ngap<5;ngap++) {
  16.         for (int i=0;i<intervalles[ngap];i++)
  17.             tri_insertion(t,intervalles[ngap],i);
  18.     }
  19. }

Les codes présentés ci-dessus ne sont pas les plus orthodoxes... Mais ils conviennent bien pour l'explication de l'algorithme. Vous trouverez des implémentations plus classiques sur rosettacode.org

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



 


La complexité du tri de Shell dépend de la suite d'incréments retenue. Les tableaux ci-dessous donnent la complexité en fonction de différents intervalles. N désigne le nombre d'éléments à trier, k le numéro d'ordre dans la liste des intervalles.

Complexité en fonction des intervalles (d'après Wikipedia)

Shell, 1959

Séquence Exemple Complexité
$$\left ( \frac{N}{2^{k}} \right )$$1, 3, 6, 12, 25, 50,100 (pour N=200) $$\Theta \left ( N^{2} \right )$$

Frank & Lazarus, 1960

Séquence Exemple Complexité
$$2\left ( \frac{N}{2^{k+1}} \right )+1$$ 1,2,3,4,7,14,26,51,101 (pour N=200) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Hibbard, 1963

Séquence Exemple Complexité
$$2^{k}-1$$1, 3, 7, 15, 31, 63, 127, 255... (A000225) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Papernov & Stasevich, 1965

Séquence Exemple Complexité
$$2^{k}+1$$, préfixé par 11, 3, 5, 9, 17, 33, 65, 129, 257... (A083318) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Pratt (1), 1971

Séquence Exemple Complexité
Nombres successifs de la forme $$2^{p}3^{q}$$ 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48... (A003586) $$\Theta \left ( N\log^{2}N \right )$$

Pratt (2), 1971

Séquence Exemple Complexité
$$\frac{\left ( 3^{k}-1 \right )}{2}$$, inférieur à N/3 1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592... (A036569) $$\Theta \left ( N^{\frac{3}{2}} \right )$$

Incerpi & Sedgewick, 1985

Séquence Exemple Complexité
a(0)=1, then a(s)=a(s-r)*b(r) for r such that C(r, 2) < s ≤ C(r+1, 2), where b() is A0365671, 4, 13, 40, 121, 364, 1093, 3280... (A003462) $$O\left ( N^{1+\sqrt{\frac{8\ln \frac{5}{2}}{\ln N}}} \right )$$

Sedgewick (1), 1986

Séquence Exemple Complexité
$$4^{k}+3*2^{k-1}+1$$1, 8, 23, 77, 281, 1073, 4193... (A036562) $$O\left ( N^{\frac{4}{3}} \right )$$

Sedgewick (2), 1986

Séquence Exemple Complexité
$$9\left ( 4^{k-1}-2^{\frac{k}{2}} \right )+1,4^{k+1}-6*2^{\frac{k+1}{2}}+1$$1, 5, 19, 41, 109, 209, 505... (A033622) $$O\left ( N^{\frac{4}{3}} \right )$$

Gonnet & Baeza-Yates, 1991

Séquence Exemple Complexité
$$h_{k}=\max \left ( \frac{5h_{k-1}}{11}, 1 \right ), h_{0}= N$$1, 2, 4, 9, 19, 41, 91 (pour N=200)

Tokuda, 1992

Séquence Exemple Complexité
$$\left ( \frac{9^{k}-4^{k}}{5*4^{k-1}} \right )$$1, 4, 9, 20, 46, 103, 233, 525... (A108870)

Ciura, 2001

Séquence Exemple Complexité
1, 4, 10, 23, 57, 132, 301, 701, 1750 (A102549)

Pigeon (1), 2000

Séquence Exemple Complexité
1, 2, 19, 103, 311, 691, 1321, 2309, 3671, 5519... (A055875)

Voir Steven Pigeon.

Pigeon(2), 2000

Séquence Exemple Complexité
$$round\left ( 1+ e^{k-2}\right )$$1, 2, 4, 8, 21, 56, 149, 404, 1098, 2982... (A055876)

Voir Steven Pigeon.

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, les intervalles à utiliser, la couleur de la courbe et cliquez sur "calculer". Jusqu'à six courbes peuvent être affichées sur le même graphique.

Calcul de la complexité du tri par la méthode de Donald Shell