Tri de Shell - Définition

Introduction

Le tri de Shell ou Shell Sort en anglais est un algorithme de tri. C'est une amélioration notable du tri par insertion au niveau de la vitesse d'exécution mais ce tri n'est pas stable. Il est facile de comprendre intuitivement comment fonctionne cet algorithme mais il est difficile de calculer son temps d'exécution.

Le nom vient de son inventeur Donald Shell (en) (né en 1924) qui publia l'algorithme dans le numéro de juillet 1959 de Communications of the ACM.

Fonctionnement

Le tri de Shell est une amélioration du tri par insertion en observant deux choses:

• Le tri par insertion est efficace si la liste est à peu près triée. (1)
• Le tri par insertion est inefficace en moyenne car il ne déplace les valeurs que d'une position par instruction. (2)

Le tri de Shell trie chaque liste d'éléments séparés de n positions chacun avec le tri par insertion. L'algorithme effectue plusieurs fois cette opération en diminuant n jusqu'à n=1 ce qui équivaut à trier tous les éléments ensemble.

Le fait de commencer avec des éléments espacés permet de pallier l'inconvénient (2), tandis que lorsque l'on fait à la fin avec un espacement de 1, ce qui est en fait un tri par insertion ordinaire, on tire parti de l'avantage (1).

Gap ou espacement entre les éléments

Les premiers espacements optimaux (empiriquement trouvés) sont les suivants : 1, 4, 10, 23, 57, 132, 301, 701.

On remarque que le facteur entre ces valeurs, exception faite des deux premières, est d'environ 2,3. On peut effectivement prolonger cette liste avec ce facteur si les dimensions du tableau dépassent environ 1600 éléments. Par exemple pour trouver le premier gap en Pascal :

        gap := 701;        while gap(liste) do gap := round(gap*2.3);      

Puis à chaque itération, si on utilise un gap calculé :

        gap := round(gap/2.3);      

Rapidité

Sur des tableaux de moins d'une centaine d'éléments, ce tri est aussi rapide qu'un tri rapide simple. Mais plutôt que d'être en compétition avec l'algorithme quicksort, il peut être utilisé pour son optimisation quand les sous-listes à traiter deviennent petites.

Le choix de l'espacement entre les éléments qu'on trie à chaque étape (gap) est très important. Il peut faire varier le temps d'exécution de O(n²) à O(nlog²n), peut-être, O(nlogn). C'est un sujet de recherche.

Exemple d'implémentation

Shell Sort en GFA BASIC

      PROCEDURE Tri_Shell(N As Int, ByRef E() As Int)        Local Int D, LIMITE, INTERVERSION, J, I        D = Div(N, 2)                  ' D = Distance de comparaison        Do                             ' BOUCLE PRINCIPALE DE SUBDIVISION DES DISTANCES          LIMITE = Sub(N, D)           '   Limite ou s'arrêtent les comparaisons          Do                           ' BOUCLE SECONDAIRE DE RECOMPARAISON EN CAS D'INTERVESION            INTERVERSION = 0           ' A priori pas d'interversion (=0)            J = D                      'J%=numéro du 2ème élément dans les comparaisons            For I = 1 To LIMITE%       ' BOUCLE de tri avec I%=1er élément de comparaison              Inc J                    '  J% suis I% en gardant la distance D%              If E(I) > E(J)           '  Si il y a lieu d'intervertir                INTERVERSION = I       '  On mémorise l"emplacement de l'interversion                Swap E(I), E(J)        '  On interverti les 2 éléments              EndIf            Next I%            LIMITE = INTERVERSION      ' Prochaine Boucle de tri s'arrêtera à la dernière interversion          Loop While INTERVERSION > 0  ' On refait des comparaisons si l'ordre des éléments a changé          Div D, 2                     ' Sinon on divise la distance par 2 et on recommence        Loop While D > 0               ' sauf si plus possible de diminuer la distance      Return      

Shell Sort en C

      /*       * Exécute un tri par insertion avec la séparation donnée       * If gap == 1, on fait un tri ordinaire.       * If gap >= length, on ne fait rien.       */      void shellSortPhase(int a[], int length, int gap) {          int i;                 for (i = gap; i < length; ++i) {              int value = a[i];              int j;              for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {                  a[j + gap] = a[j];              }              a[j + gap] = value;          }      }             void shellSort(int a[], size_t length) {          /*           * gaps[] doit approximer une Série géométrique.           * La sequence suivante est la meilleure connue en terme           * de nombre moyen de comparaisons. voir:           * http://www.research.att.com/~njas/sequences/A102549           */          static const int gaps[] = {              1, 4, 10, 23, 57, 132, 301, 701          };          int sizeIndex;                 for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;                     sizeIndex >= 0;                     --sizeIndex)              shellSortPhase(a, length, gaps[sizeIndex]);      }      

Shell Sort en C++

        /* Réadaptation du code précédent en C++, avec template pour pouvoir s'adapter           à tout type de donnée pour lequel les opérateur '==', '<' et '>' sont définis. */               template<typename T> void SHELLSRT_phase(T* a, unsigned int size, unsigned int gap)         {          for (int i = gap; i < (int)size; ++i)           {            T value = a[i];            int tmp = i - gap;            int j = 0;                   for(j = tmp; ((j >= 0) && (a[j] > value)); j -= gap)               a[j + gap] = a[j];                   a[j + gap] = value;          }        }               template<typename T> void SHELLSRT_make(T* a, unsigned int size)         {          static const unsigned int gaps[9] = {1, 4, 10, 23, 57, 132, 301, 701, 1750};                 unsigned int tmp = 9 -1;                 for(unsigned int i = tmp; i != -1; --i)            SHELLSRT_phase(a, size, gaps[i]);        }      

Shell sort en Pascal

Implémention du tri Shell en Pascal (par ordre croissant).

      procedure TriShell(n : integer ; var t : tab);      var        p, k, i, j, x : integer;      begin        (* Recherche du Gap optimal qui est le résultat de *)        (* la suite récurrente: Un = 3.Un-1 + 1           *)        (* Tel que Un < n (Nombre d'éléments du tableau)   *)        p := 0;        while (p < n) do p := 3 * p + 1;               while (p <> 1) do        begin          (* On affine peu à peu le Gap            *)          (* Gap = 1 ==> Tri par Insertion ordinaire *)          p := p div 3;          if (p=1) then                       x:=1                    else                       x:=n-(n mod p)+1;          for i := x to n do          begin            k := t[i]; (* Valeur à insérer *)                   (* Recherche de la position d'insertion *)            j:= i;            while (j >= p ) and (t[j - p] > k) do            begin              t[j] := t[j - p];              j := j - p;            end;                   (* Insertion de la valeur à son emplacement *)            t[j] := k;          end;        end;      end;      

Shell Sort en Java

      public static void triDeShell(int [] tab,int tailleLogique){         int pas = 1;         while( pas < tailleLogique/9) {            pas = pas*3 + 1; // on fixe le premier pas         }         while (pas > 0) {  // boucle sur les différents pas                     for(int série = 0; série <= pas-1; série ++) {  // boucle sur les séries               int positionEltAInsérer = série + pas;  // tri par insertion                      while(positionEltAInsérer < tailleLogique) {                  int élémentAInsérer = tab[positionEltAInsérer];                  int posElemComparé = positionEltAInsérer - pas;                         while ((posElemComparé >= 0) && (élémentAInsérer < tab[posElemComparé])) {                     tab[posElemComparé + pas] = tab[posElemComparé];                     posElemComparé -= pas;                  }                  tab [posElemComparé + pas] = élémentAInsérer;                  positionEltAInsérer += pas;               }            }         		         pas = pas/3;	         }            }      

Shell Sort en C#

      using System;      public class ShellSorter      {        public void Sort(int [] list)                      {            int inc;            for(inc=1;inc<=list.Length/9;inc=3*inc+1);            for(;inc>0;inc/=3)            {                for(int i=inc+1;i<=list.Length;i+=inc)              {                int t=list[i-1];                int j=i;                while((j>inc)&&(list[j-inc-1]>t))                {                  list[j-1]=list[j-inc-1];                  j-=inc;                }                list[j-1]=t;              }            }          }      }      public class MainClass      {          public static void Main()          {          int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};          ShellSorter sh=new ShellSorter();          sh.Sort(iArrary);          for(int m=0;m<=13;m++)          Console.WriteLine("{0}",iArrary[m]);             }      }