Implémentation d'algorithmes classiques/Algorithmes de tri/Tri de Shell

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

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]);
}

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]);
  }

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;

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;
   }
}

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]); 
      }
}

Tout ou partie de cette page est issue de l'article Wikipédia « Tri de Shell » dans sa version du 2 juillet 2010.