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 Free Pascal suivant :

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