Section courante

A propos

Section administrative du site

La technique de tri nommée «Shell-Metzner», est en fait une technique de réduction du nombre de comparaison a effectuer pour trier un tableau. Comment si prend-on? C'est simple, la comparaison s'effectue entre 2 éléments séparé par un écart égal (au départ) à la moitié de la taille du tableau. Ensuite, la comparaison s'effectue entre des éléments séparées par un écart égal au nombre d'élément du tableau divisée par 4. Lorsque l'écart atteint finalement 1, la tri est terminé. Vous trouverez la réponse que vous souhaitez, à l'aide du code source Delphi suivant :

  1. Program ShellTri;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. Uses SysUtils;
  6.  
  7. Const
  8.  Tableau : Array[0..7] of Byte = (15, 10, 23, 2, 8, 9, 14, 16);
  9.  
  10. Var
  11.  K,L,I,J,T:Byte;
  12.  Inversion,Ecart:Integer;
  13.  
  14. BEGIN
  15.  Write('Avant:');
  16.  For K := 0 to High(Tableau) do Begin
  17.   Write(Tableau[K],', ');
  18.  End;
  19.  
  20.  Inversion := 0;
  21.  Ecart := High(Tableau) + 1;
  22.  Repeat
  23.   Ecart := Ecart shr 1;
  24.   Repeat
  25.    Inversion := 0;
  26.    For I := 0 to (High(Tableau) + 1) - Ecart - 1 do Begin
  27.     J := I + Ecart;
  28.     If(Tableau[J] < Tableau[I])Then Begin
  29.      T := Tableau[I];
  30.      Tableau[I] := Tableau[J];
  31.      Tableau[J] := T;
  32.      Inversion := 1;
  33.     End;
  34.    End;
  35.   Until 1 <> Inversion;
  36.  Until 1 = Ecart;
  37.  
  38.  WriteLn;
  39.  Write('Après:');
  40.  For L := 0 to High(Tableau) do Begin
  41.   Write(Tableau[L],', ');
  42.  End;
  43.  WriteLn;
  44. END.

on obtiendra le résultat suivant :

Avant:15, 10, 23, 2, 8, 9, 14, 16,
Après:2, 8, 9, 10, 14, 15, 16, 23,

Voir également

Algorithme - Tri

Dernière mise à jour : Dimanche, le 17 août 2014