Donald L. Shell proposa, en 1959, une variante du tri par insertion. Ce tri consiste à trier séparément des sous-suites de la table, formées par les éléments répartis de h en h. Empiriquement, Shell propose la suite d'incréments vérifiant h1 = 1, hn+1 = 3hn+1 en réalisant les tris du plus grand incrément possible vers le plus petit.
Dans la démo ci-dessous - en raison de la faible taille de la table à trier - on a choisi h1=1, h2=2, h3=4, h4=5, h5=10.
Votre navigateur ne peut pas lancer cette applet !
--------------------------------------------------------------------------------
Voici, en Caml, l'algorithme du tri Shell :
let tri vecteur h = let i = ref 0 and j = ref 0 in
for k=0 to (h-1) do
begin
i:=k+h;
while (!i < vect_length(vecteur)) do
let x = vecteur.(!i) in
begin
j:=!i - h;
while (!j>=0) && vecteur.(!j)>x do
vecteur.(!j+h) <- vecteur.(!j);
j:=!j - h;
vecteur.(!j + h) <- x;
done;
i:=!i + h;
end
done;
end
done;;
let tri_shell vecteur = let h = ref 1 and l = vect_length(vecteur)+1 in
begin
while !h<(l/9) do h:=3 * !h + 1;done;
while (!h>0) do
begin
tri vecteur !h;
h:=!h / 3;
end
done;
end;;
tri : 'a vect -> int -> unit = fun
tri_shell : 'a vect -> unit = fun
--------------------------------------------------------------------------------
La complexité du tri par Shell est en O(n2) dans le pire des cas.
Le graphique ci-contre montre la progression du nombre d'instruction en fonction de la taille des données.
Mer 13 Fév - 9:53