Tri de Shell

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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. Le principe de l'algorithme est simple mais l'étude du temps d'exécution est très complexe, et plusieurs problèmes sont toujours ouvert à ce sujet.

Le nom vient de son inventeur Donald Shell (en) (né en 1924) qui publia l'algorithme dans le numéro de juillet 1959 de Communications of the ACM.

Principe[modifier | modifier le code]

Amélioration du tri par insertion[modifier | modifier le code]

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).

Gap ou espacement entre les éléments[modifier | modifier le code]

Les premiers espacements optimaux (empiriquement trouvés) sont les suivants : 1, 4, 10, 23, 57, 132, 301, 701.

On remarque que le facteur entre ces valeurs, exception faite des deux premières, est d'environ 2,3. On peut effectivement prolonger cette liste avec ce facteur si les dimensions du tableau dépassent environ 1600 éléments. Par exemple pour trouver le premier gap en Pascal :

  gap := 701;
  while gap<length(liste) do gap := round(gap*2.3);

Puis à chaque itération, si on utilise un gap calculé :

  gap := round(gap/2.3);

Jusqu'à arriver à 701, où l'on reprends la liste des espacements optimaux évoquée plus haut.

Complexité[modifier | modifier le code]

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^2) à O(n\log^2 n) et peut-être même O(n\log n) (problème ouvert).

Des bornes inférieures ont aussi été publiées, on peut citer une borne de O(n ({\log n \over \log \log n})^2) quels que soient les espacements[1].

Notes et références[modifier | modifier le code]

  1. C. Greg Plaxton, Bjarne Poonen et Torsten Suel, « Improved Lower Bounds for Shellsort », dans Annual Symposium on Foundations of Computer Science, vol. 33,‎ 1992 (DOI 10.1109/SFCS.1992.267769), p. 226–235

Liens externes[modifier | modifier le code]

Sur les autres projets Wikimedia :