Le tri de Shell

Algorithmique > Algorithmes de tri > Tri de Shell [ Réagir ]

Principe et optimisation

Le tri de Shell est une évolution du tri par insertion. En effet, on parcourt le tableau en utilisant un "pas" (c'est-à-dire un filtre) de plus en plus petit (donc de moins en moins grossier). Au dernier passage, on applique un "pas" de valeur 1 (ce qui équivaut à faire un tri par insertion sur un tableau presque trié et est donc assez rapide).

L'efficacité de cet algorithme est étroitement liée au choix des "pas" ou filtres successifs. Afin d'obtenir un code portable, il vaut mieux choisir une suite (de préférence géométrique ou composée). Cependant, certaines séries sont connues pour être encore plus efficace (notamment la suite : 1, 4, 10, 23, 57, 132, 301, 701).

Complexité en temps

Le tri de Shell a une complexité en temps de la forme Ω(n²). Cependant, il est plus rapide que le tri par insertion.

Conditions et évolutions

Bien que ce tri soit tout de même assez lent en comparaison avec des algorithmes plus complexes, le tri Shell peut être utilisé sans conditions particulières. Vous pouvez l'adapter à vos besoins :

• Pour trier autre chose que des entiers, il suffit de modifier la déclaration de TMyType.
• Pour changer la fonction de compaison, il faut adapter la fonction Compare().
  Celle-ci renvoie "TRUE" si un élément de valeur aV doit être placé avant l'élément de valeur aW dans le tableau trié.

Code (Pascal)

type TMyType = Int64;

procedure ShellSort(var A: Array of TMyType; N: Integer);

  function Compare(aV,aW: TMyType): Boolean;
  begin
    Result:=(aV<aW);
  end;

var Pas,I,J: Integer;
    Tmp: TMyType;
begin

  Pas:=0;
  While (Pas<N) do Pas:=3*Pas+1;

  While (Pas>0) do
    begin
      Pas:=Pas div 3;
      For I:= Pas to N-1 do
        begin
          Tmp:=A[I];
          J:=I-Pas;
          While ((J>=0) and Compare(Tmp,A[J])) do
            begin
              A[J+Pas]:=A[J];
              J:=J-Pas;
            end;
          A[J+Pas]:=Tmp;
        end;
    end;

end;