Section courante

A propos

Section administrative du site

Tri de Shell-Metzner

Le tri de Shell-Metzner, ou plus simplement tri de Shell (du nom de son inventeur Donald Shell en 1959), est une amélioration du tri par insertion, conçue pour augmenter son efficacité sur les grandes listes. Il fonctionne en divisant la liste à trier en sous-séries d'éléments séparés par un certain écart (ou "gap"), diminuant progressivement. Au sein de chaque sous-série, les éléments sont triés localement. Au fur et à mesure que l'écart est réduit, les sous-séries se rapprochent, jusqu'à ce que l'écart atteigne 1, ce qui équivaut à un tri par insertion final sur la liste entière. Ce procédé permet de déplacer rapidement les éléments sur de longues distances, ce qui accélère la convergence vers une liste triée.

Principe du tri de Shell-Metzner

Le tri de Shell-Metzner, ou tri de Shell, est une amélioration du tri par insertion, conçue pour mieux gérer les grandes quantités de données. Il utilise une technique de gap sequence (séquence d'écart), commençant par des comparaisons d'éléments éloignés avant de réduire progressivement ces écarts. L'idée est de trier les sous-séries d'éléments dans un premier temps, puis d'affiner l'ordre au fur et à mesure que l'écart diminue, ce qui permet de réduire les déplacements d'éléments vers leur position finale. Cette technique rend le tri de Shell beaucoup plus rapide que le tri par insertion classique pour les grandes listes de données non triées.

L'algorithme de Shell commence par définir un écart initial, souvent égal à la moitié de la taille du tableau, et divise ainsi le tableau en plusieurs sous-listes. Chaque sous-liste est triée individuellement en utilisant un tri par insertion. Ensuite, l'écart est réduit, et le processus est répété pour les nouvelles sous-listes générées. Au fur et à mesure que l'écart diminue, les sous-listes se rapprochent de l'ensemble complet, jusqu'à ce que l'écart atteigne finalement 1, moment auquel le tri final est effectué.

L'efficacité du tri de Shell dépend de la séquence d'écarts utilisée. Différentes séquences ont été étudiées pour améliorer la performance de l'algorithme, comme les séquences de Hibbard, Sedgewick ou de Knuth. Chaque séquence a ses avantages et inconvénients, mais elles partagent le même principe de réduire progressivement les écarts de manière à optimiser le nombre de comparaisons et de déplacements d'éléments dans le tableau. Par exemple, la séquence de Knuth, 3k-1, est réputée pour ses performances équilibrées dans la plupart des cas.

L'un des avantages du tri de Shell est qu'il devient très efficace lorsque les données sont partiellement triées. Contrairement à d'autres méthodes comme le tri rapide, le tri de Shell fonctionne bien pour les structures de données modérément ou très dispersées. En réduisant progressivement les déplacements d'éléments nécessaires pour atteindre leur position finale, l'algorithme limite le nombre d'opérations, ce qui rend le tri rapide même avec des listes de grande taille.

Voici les points principales du principe de fonctionnement du tri de Shell-Metzner :

Avantages et complexité

Le tri de Shell-Metzner est plus rapide que le tri par insertion traditionnel, notamment sur de grands ensembles de données, bien qu'il ait une complexité de temps variable en fonction de la séquence d'écarts choisie. Certaines séquences, comme celles de Hibbard ou de Sedgewick, améliorent son efficacité, réduisant la complexité temporelle dans le meilleur des cas à environ O(n3/2) voire moins avec certaines optimisations.

Algorithme

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éparer 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 terminer.

Écart ← Nombre d'élément
BOUCLE FAIRE
   Écart ← Écart / 2
   BOUCLE FAIRE
      Inversion ← Faux
      BOUCLE POUR I ← 1 JUSQU'A Nombre d'élément - Écart
         J ← I + Écart
         SI Tableau [J] < Tableau [I] ALORS
            Temporaire ← Tableau[I]
            Tableau[I] ← Tableau[J]
            Tableau[J] ← Temporaire
            Inversion ← Vrai
         FIN SI
      FIN BOUCLE POUR
   TANT QUE N'EST PAS Inversion
TANT QUE Écart = 1

Exemple en langage de programmation Turbo Pascal

Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en Turbo Pascal :

  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,

Exemple en langage de programmation C

Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en C :

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MaxTableau 8
  5.  
  6. int main()
  7. {
  8.     int K,L,I,J,Inversion,ecart,Temporaire;
  9.     int Tableau[MaxTableau] = {15, 10, 23, 2, 8, 9, 14, 16};
  10.     printf("Avant:");
  11.  
  12.     for(K = 0; K < MaxTableau; K++) printf("%i, ",Tableau[K]);
  13.  
  14.     Inversion = 0;
  15.     ecart = MaxTableau;
  16.     do {
  17.         ecart >>= 1;
  18.         do {
  19.             Inversion = 0;
  20.             for(I = 0; I <= MaxTableau - ecart - 1; I++) {
  21.                 J = I + ecart;
  22.                 if(Tableau[J] < Tableau[I]) {
  23.                     Temporaire = Tableau[I];
  24.                     Tableau[I] = Tableau[J];
  25.                     Tableau[J] = Temporaire;
  26.                     Inversion = 1;
  27.                 }
  28.             }
  29.         } while (1 == Inversion);
  30.     } while (1 != ecart);
  31.  
  32.     printf("\nAprès:");
  33.     for(L = 0; L < MaxTableau; L++) {
  34.         printf(", %i",Tableau[L]);
  35.     }
  36.     printf("\n");
  37.     return 0;
  38. }

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,

Exemple en langage de programmation C#

Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en C# :

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace TriShell
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             const int MaxTableau = 8 ;
  13.             int K,L,I,J,Inversion,ecart,Temporaire;
  14.             int[] Tableau = {15, 10, 23, 2, 8, 9, 14, 16};
  15.             Console.Write("Avant:");
  16.             for(K = 0; K < MaxTableau; K++) Console.Write(Tableau[K] + ", ");
  17.             Inversion = 0;
  18.             ecart = MaxTableau;
  19.             do {
  20.                 ecart >>= 1;
  21.                 do {
  22.                     Inversion = 0;
  23.                     for(I = 0; I <= MaxTableau - ecart - 1; I++) {
  24.                         J = I + ecart;
  25.                         if(Tableau[J] < Tableau[I]) {
  26.                             Temporaire = Tableau[I];
  27.                             Tableau[I] = Tableau[J];
  28.                             Tableau[J] = Temporaire;
  29.                             Inversion = 1;
  30.                         }
  31.                     }
  32.                 } while (1 == Inversion);
  33.             } while (1 != ecart);
  34.             Console.WriteLine();
  35.             Console.Write("Après:");
  36.             for(L = 0; L < MaxTableau; L++) {
  37.                 Console.Write(", " + Tableau[L]);
  38.             }
  39.             Console.WriteLine(); 
  40.         }
  41.     }
  42. }
  43.  

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,

Exemple en langage de programmation Delphi

Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en Delphi :

  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,


Dernière mise à jour : Dimanche, le 12 mars 2006