Tri de Shell ( shell sort)

Variante du tri par insertion, T(n) = O(n²) en moyenne. 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 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).

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 :

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

procedure TriShell(n : integer ; var t : tab);

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 <> 0) do

  begin

    (* On affine peu à peu le Gap            *)

    (* Gap = 1 ==> Tri par Insertion ordinaire *)

    p := p div 3;

    for i := p to n do

    begin

      k := t[i]; (* Valeur à insérer *)

      (* Recherche de la position d'insertion *)

      j:= i;