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

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

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

type
  arrayOfInteger = array of integer;

procedure TriShell(n : integer ; t : arrayOfInteger);
var
  p, k, i, j : 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;
    for i := p to n-1 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;

Implémentation du tri Shell en Python (par ordre croissant).

def triInsertion(tab, i0=0, dec=1):
    """
    Trie un tableau à l'aide de l'algorithme de tri par insertion...

    Par défaut, trie l'ensemble du tableau.
    Si i0 et dec sont spécifiés, trie les cases d'indices i0, i0 + dec, i0 + 2dec, i0 + 3dec...

    - Paramètre tab : tableau à trier,
    - Paramètre i0 : indice de la première case à trier
    - Paramètre dec : décalage entre deux cases à trier
    - Ne renvoie rien (modifie le tableau en place)
    """
    for i in range(i0 + dec, len(tab), dec):
        tempo = tab[i]
        j = i   # indice de la case libre
        while j > i0 and tab[j-dec] > tempo:
            tab[j] = tab[j-dec]
            j = j - dec
        tab[j] = tempo

from math import log, floor

def triShell(tab):
    """
    Trie un tableau à l'aide de l'algorithme de tri de Shell

    - Paramètre tab : tableau à trier
    - Ne renvoie rien.
    """
    for k in range(floor(log(len(tab), 2)), 0, -1):
        dec = 2**k - 1
        for i in range(0, dec):
            triInsertion(tab, i, dec)

Implémention du tri Shell en Ruby.

module ShellSort
    def self.sort(keys)
        sort!(keys.clone)
    end
    
    def self.sort!(keys)
        gap = keys.size/2
        while gap > 0
            for j in gap...keys.size
                key = keys[j]
                i = j
                    while (i >= gap and keys[i-gap] > key)
                    keys[i] = keys[i-gap]
                    i -= gap
                    end
                keys[i] = key
            end
            gap /= 2
        end
        keys
    end
end

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