La technique de tri connue sous le nom de «Shell-Metzner», plus souvent appelée simplement «Shell Sort», constitue une amélioration ingénieuse des méthodes de tri par échanges successifs. Son objectif principal est de réduire considérablement le nombre de comparaisons et de permutations nécessaires pour remettre un tableau dans l'ordre. Contrairement au tri à bulles, qui compare essentiellement des éléments adjacents, le tri Shell commence par comparer des éléments éloignés les uns des autres. Cette approche permet de déplacer rapidement les valeurs très mal positionnées vers leur emplacement approximatif avant d'effectuer les ajustements finaux.
Le principe de fonctionnement est relativement simple. Dans un premier temps, le tableau est divisé virtuellement en plusieurs sous-groupes grâce à un écart, souvent appelé « gap ». Cet écart correspond généralement à la moitié de la taille totale du tableau. Les comparaisons sont alors réalisées entre des éléments séparés par cette distance fixe. Une fois ce passage terminé, l'écart est réduit progressivement, par exemple en le divisant par deux à chaque étape. Les comparaisons sont alors répétées avec des éléments de plus en plus rapprochés. Ce processus continue jusqu'à ce que l'écart atteigne la valeur 1, moment où le tableau est pratiquement ordonné et où les dernières corrections sont effectuées.
Cette stratégie permet d'obtenir de meilleures performances que plusieurs algorithmes de tri élémentaires. En effet, une grande partie du travail est accomplie dès les premières étapes, lorsque les écarts sont importants. Les éléments éloignés de leur position finale peuvent ainsi être déplacés rapidement, ce qui réduit le nombre total d'opérations nécessaires lors des passages suivants. Pour cette raison, le tri Shell est souvent considéré comme un excellent compromis entre simplicité d'implantation et efficacité.
À l'aide du code source Delphi présenté ci-dessous, vous découvrirez comment appliquer cette méthode sur un tableau de nombres. Le programme affiche tout d'abord le contenu initial du tableau, puis exécute les différentes phases de tri en réduisant progressivement l'écart entre les éléments comparés. Enfin, il affiche le tableau complètement trié, permettant ainsi de constater l'efficacité de cette technique classique de classement de données :
- Program ShellTri;
-
- {$APPTYPE CONSOLE}
-
- Uses SysUtils;
-
- Const
- Tableau : Array[0..7] of Byte = (15, 10, 23, 2, 8, 9, 14, 16);
-
- Var
- K,L,I,J,T:Byte;
- Inversion,Ecart:Integer;
-
- BEGIN
- Write('Avant:');
- For K := 0 to High(Tableau) do Begin
- Write(Tableau[K],', ');
- End;
-
- Inversion := 0;
- Ecart := High(Tableau) + 1;
- Repeat
- Ecart := Ecart shr 1;
- Repeat
- Inversion := 0;
- For I := 0 to (High(Tableau) + 1) - Ecart - 1 do Begin
- J := I + Ecart;
- If(Tableau[J] < Tableau[I])Then Begin
- T := Tableau[I];
- Tableau[I] := Tableau[J];
- Tableau[J] := T;
- Inversion := 1;
- End;
- End;
- Until 1 <> Inversion;
- Until 1 = Ecart;
-
- WriteLn;
- Write('Après:');
- For L := 0 to High(Tableau) do Begin
- Write(Tableau[L],', ');
- End;
- WriteLn;
- 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,