AccueilđŸ‡«đŸ‡·Chercher

Tri de Shell

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 ouverts à ce sujet.

Tri de Shell
Exemple du tri de Shell avec les espacements 23, 10, 4, 1
DĂ©couvreur ou inventeur
Donald Shell (en)[1]
Date de découverte
ProblÚmes liés
Algorithme de tri, algorithme en place (en), tri par comparaison (en)
Structure des données
Complexité en temps
Pire cas
[2]
Moyenne
[3]
Meilleur cas
[3]
Complexité en espace
Pire cas
[3]
Tri de Shell barres de couleur de l'algorithme

Le nom vient de son inventeur Donald Shell (en) (1924-2015) qui publia l'algorithme dans le numéro de de Communications of the ACM[4].

Principe

Amélioration du tri par insertion

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

Code Python

tab = [701, 301, 132, 57, 23, 10, 4, 1]
def shell_sort(tab):
  n = len(tab)
  for m in tab:
    for r in range(m):
      # tri par insertion des positions de la forme k * m + r
      for i in range (r + m, n, m):
        j = i
        x = tab[i]
        while j > r and tab[j-m] > x:
          tab[j] = tab[j-m]
          j = j - m
        tab[j] = x

Gap ou espacement entre les éléments

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

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 étendre la liste gaps jusqu'à la taille nécessaire:

gap = gaps[0]
while gap<length(liste):
  gap = round(gap*2.3);
  gaps = [gap] + gaps

Des espacements de la forme , dans l'ordre croissant, garantissent quant à eux la meilleure complexité théorique prouvée aujourd'hui, [6].

Complexité

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 la suite des espacements entre les Ă©lĂ©ments qu'on trie Ă  chaque Ă©tape (gap) est trĂšs important. Il peut faire varier la complexitĂ© dans le pire cas de Ă  [6]. Il est Ă©galement possible que la complexitĂ© en moyenne puisse ĂȘtre avec un bon choix d'espacements (problĂšme ouvert).

Des bornes inférieures ont aussi été publiées, on peut citer une borne de sur la complexité dans le pire cas quels que soient les espacements[7].

Le tableau suivant compare les gaps publiés jusqu'à aujourd'hui :

OEIS Terme gĂ©nĂ©ral (k ≄ 1) Gaps ou espacements concrets ComplexitĂ© dans le pire des cas Auteur et annĂ©e de publication
[i.e quand N = 2p] Donald Shell (en), 1959
Frank & Lazarus, 1960[8]
A168604 Thomas N. Hibbard (en), 1963[9]
A083318 , préficé avec 1 Papernov & Stasevich, 1965[10]
A003586 Nombres successifs de la forme (entier friable 3-lisse) Vaughan Ronald Pratt (en), 1971[6]
A003462 , plus petit que Vaughan Ronald Pratt (en), 1971[6]
A036569 Incerpi & Robert Sedgewick, 1985[11], Knuth[12]
A036562 , préfixé par 1 Sedgewick, 1986[13]
A033622 Sedgewick, 1986[14]
Inconnue Gaston Gonnet (en) & Ricardo Baeza-Yates (en), 1991[15]
A108870 Inconnue Tokuda, 1992[16]
A102549 Inconnue (trouvé expérimentalement) Inconnue Ciura, 2001[17]

Références

  1. (en) D. L. Shell, « A high-speed sorting procedure », Communications of the ACM, New York, ACM, vol. 2, no 7,‎ , p. 30-32 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/368370.368387)
  2. en">Vaughan Pratt (en), « Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) »
  3. « https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html »
  4. (en) ShellD L, « A high-speed sorting procedure », Communications of the ACM,‎ (DOI 10.1145/368370.368387, lire en ligne, consultĂ© le )
  5. Marcin Ciura, « Best Increments for the Average Case of Shellsort », dans Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, Springer, (ISBN 3540424873, lire en ligne), p. 106–117
  6. Vaughan Pratt (en), Shellsort and sorting networks, Garland Pub, , 59 p. (ISBN 0-8240-4406-1, OCLC 5008158, lire en ligne)
  7. C. Greg Plaxton, Bjarne Poonen et Torsten Suel, « Improved Lower Bounds for Shellsort », dans Annual Symposium on Foundations of Computer Science, vol. 33, (DOI 10.1109/SFCS.1992.267769), p. 226–235
  8. Frank R. M. et R. B. Lazarus, « A High-Speed Sorting Procedure », Communications of the ACM, vol. 3, no 1,‎ , p. 20–22 (DOI 10.1145/366947.366957)
  9. Thomas N. Hibbard, « An Empirical Study of Minimal Storage Sorting », Communications of the ACM, vol. 6, no 5,‎ , p. 206–213 (DOI 10.1145/366552.366557)
  10. A. A. Papernov et G. V. Stasevich, « A Method of Information Sorting in Computer Memories », Problems of Information Transmission, vol. 1, no 3,‎ , p. 63–75 (lire en ligne)
  11. Janet Incerpi et Robert Sedgewick, « Improved Upper Bounds on Shellsort », Journal of Computer and System Sciences, vol. 31, no 2,‎ , p. 210–224 (DOI 10.1016/0022-0000(85)90042-x)
  12. Donald E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, Reading, Massachusetts, Addison-Wesley, , 83–95 p. (ISBN 0-201-89685-0), « Shell's method »
  13. Robert Sedgewick, Algorithms in C, vol. 1, Addison-Wesley, , 273–281 p. (ISBN 0-201-31452-5)
  14. Robert Sedgewick, « A New Upper Bound for Shellsort », Journal of Algorithms, vol. 7, no 2,‎ , p. 159–173 (DOI 10.1016/0196-6774(86)90001-5)
  15. Gaston H. Gonnet et Ricardo Baeza-Yates, Handbook of Algorithms and Data Structures : In Pascal and C, Reading, Massachusetts, Addison-Wesley, , 2e Ă©d., 161–163 p. (ISBN 0-201-41607-7), « Shellsort »
  16. Naoyuki Tokuda, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture, Amsterdam, North-Holland Publishing Co., , 449–457 p. (ISBN 0-444-89747-X), « An Improved Shellsort »
  17. Marcin Ciura, Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, London, Springer-Verlag, , 106–117 p. (ISBN 3-540-42487-3), « Best Increments for the Average Case of Shellsort »

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.