Voir la source de Tri de Shell

{{Infobox Algorithme
| structure des données = [[liste (informatique)|liste]] ou [[tableau (structure de données)|tableau]]
}}

[[Fichier:Shell sorting algorithm color bars.svg|vignette|Tri de Shell barres de couleur de l'algorithme]]
Le '''tri de Shell''' ou '''''{{langue|en|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.

Le nom vient de son inventeur {{Lien|langue=en|fr=Donald Shell}} (1924-2015) qui publia l'algorithme dans le numéro de {{date|juillet 1959}} de ''[[Communications of the ACM]]''<ref>{{Article |langue=EN |prénom1=ShellD |nom1=L |titre=A high-speed sorting procedure |périodique=Communications of the ACM |date=1959-07-01 |doi=10.1145/368370.368387 |lire en ligne=https://dl.acm.org/doi/abs/10.1145/368370.368387 |consulté le=2020-05-09 }}</ref>.

== 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 [[Complexité en moyenne des algorithmes|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 ===

<syntaxhighlight lang="python3" line="0">

gaps = [701, 301, 132, 57, 23, 10, 4, 1]

def shell_sort(tab):
  n = len(tab)
  for m in gaps:
    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
</syntaxhighlight>

=== 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<ref name = "Ciura">{{chapitre
  |lire en ligne=http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf
  |titre ouvrage =Proceedings of the 13th International Symposium on Fundamentals of Computation Theory
  |prénom1=Marcin  
  |nom1=Ciura
  |titre chapitre=Best Increments for the Average Case of Shellsort
  |éditeur=Springer
  |année=2001
  |passage=106–117
  |isbn=3540424873}}</ref>.

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:
<syntaxhighlight lang="python3" line="1">
gap = gaps[0]
while gap<length(liste):
  gap = round(gap*2.3);
  gaps = [gap] + gaps 
</syntaxhighlight>

Des espacements de la forme <math>2^p3^q</math>, dans l'ordre croissant, garantissent quant à eux la meilleure complexité théorique prouvée aujourd'hui, <math>O(n \log^2 n)</math><ref name="Pratt">{{Ouvrage|auteur1=[[Vaughan Pratt]]|titre=Shellsort and sorting networks|éditeur=Garland Pub|année=1979|pages totales=59|isbn=0-8240-4406-1|oclc=5008158|lire en ligne=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0740110}}</ref>.

== 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 [[tri rapide|''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é en temps|complexité dans le pire cas]] de <math>O\left(n^2\right)</math> à <math>O\left(n\log^2 n \right)</math><ref name="Pratt" />. Il est également possible que la [[Complexité en moyenne des algorithmes|complexité en moyenne]] puisse être <math>O\left(n\log n \right)</math> avec un bon choix d'espacements (problème ouvert).

Des bornes inférieures ont aussi été publiées, on peut citer une borne de <math>\Omega\left(n \left({\log n \over \log \log n}\right)^2 \right)</math> sur la complexité dans le pire cas quels que soient les espacements<ref>
{{chapitre
  |nom1=Plaxton |prénom1=C. Greg
  |nom2=Poonen |prénom2=Bjarne
  |nom3=Suel |prénom3=Torsten
  |titre chapitre =Improved Lower Bounds for Shellsort
  |titre ouvrage =Annual Symposium on Foundations of Computer Science
  |volume=33
  |année=1992
  |passage=226–235
  |doi=10.1109/SFCS.1992.267769
}}</ref>.

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

:{| class="wikitable"
|- style="background-color: #efefef;"
! [[OEIS]]
! Terme général (''k'' ≥ 1)
! Gaps ou espacements concrets
! Complexité dans le pire des cas
! Auteur et année de publication
|----
|
| <math>\left\lfloor\frac{N}{2^k}\right\rfloor</math>
| <math>\left\lfloor\frac{N}{2}\right\rfloor,
        \left\lfloor\frac{N}{4}\right\rfloor, \ldots, 1
  </math>
| <math>\Theta\left(N^2\right)</math> [i.e quand ''N'' = 2<sup>''p''</sup>]
| {{Lien|langue=en|fr=Donald Shell}}, 1959
|----
|
| <math>2 \left\lfloor\frac{N}{2^{k+1}}\right\rfloor + 1</math>
| <math>2 \left\lfloor\frac{N}{4}\right\rfloor + 1, \ldots, 3, 1</math>
| <math>\Theta\left(N^\frac{3}{2}\right)</math>
| Frank & Lazarus, 1960<ref>{{article
  |prénom1=Frank
  |nom1=R. M.
  |nom2=Lazarus
  |prénom2=R. B.
  |titre=A High-Speed Sorting Procedure
  |journal=Communications of the ACM
  |volume=3
  |numéro=1
  |année=1960
  |passage=20–22
  |doi=10.1145/366947.366957}}</ref>
|----
| [[OEIS:A168604|A168604]]
| <math>2^k - 1</math>
| <math>1, 3, 7, 15, 31, 63, \ldots</math>
| <math>\Theta\left(N^\frac{3}{2}\right)</math>
| {{Lien|langue=en|fr=Thomas N. Hibbard}}, 1963<ref>{{article
  |nom=Hibbard
  |prénom=Thomas N.
  |titre=An Empirical Study of Minimal Storage Sorting
  |journal=Communications of the ACM
  |volume=6
  |numéro=5
  |année=1963
  |passage =206–213
  |doi=10.1145/366552.366557}}</ref>
|----
| [[OEIS:A083318|A083318]]
| <math>2^k + 1</math>, préfixé avec 1
| <math>1, 3, 5, 9, 17, 33, 65, \ldots</math>
| <math>\Theta\left(N^\frac{3}{2}\right)</math>
| Papernov & Stasevich, 1965<ref>{{article
  |url=http://www.mathnet.ru/links/83f0a81df1ec06f76d3683c6cab7d143/ppi751.pdf
  |nom=Papernov
  |prénom=A. A.
  |nom2=Stasevich
  |prénom2=G. V.
  |titre=A Method of Information Sorting in Computer Memories
  |journal=Problems of Information Transmission
  |volume=1
  |numéro=3
  |année=1965
  |pages=63–75}}</ref>
|----
| [[OEIS:A003586|A003586]]
| Nombres successifs de la forme <math>2^p 3^q</math> ([[entier friable]] 3-lisse)
| <math>1, 2, 3, 4, 6, 8, 9, 12, \ldots</math>
| <math>\Theta\left(N \log^2 N\right)</math>
| {{Lien|langue=en|fr=Vaughan Ronald Pratt}}, 1971<ref name="Pratt"/>
|----
| [[OEIS:A003462|A003462]]
| <math>\frac{3^k - 1}{2}</math>, plus petit que <math>\left\lceil\frac{N}{3}\right\rceil</math>
| <math>1, 4, 13, 40, 121, \ldots </math>
| <math>\Theta\left(N^\frac{3}{2}\right)</math>
| {{Lien|langue=en|fr=Vaughan Ronald Pratt}}, 1971<ref name="Pratt"/>
|----
| [[OEIS:A036569|A036569]]
| <math>\begin{align}
           &\prod\limits_I a_q, \hbox{où} \\
  a_q = {} &\min\left\{n \in \mathbb{N}\colon n \ge \left(\frac{5}{2}\right)^{q+1}, \forall p\colon 0 \le p < q \Rightarrow pgcd(a_p, n) = 1\right\} \\
    I = {} &\left\{0 \le q < r \mid q \neq \frac{1}{2}\left(r^2 + r\right) - k \right\} \\
    r = {} &\left\lfloor \sqrt{2k + \sqrt{2k}} \right\rfloor
\end{align}</math>
| <math>1, 3, 7, 21, 48, 112, \ldots</math>
| <math>O\left(N^{1 + \sqrt{\frac{8\ln\left(5/2\right)}{\ln(N)}}}\right)</math>
| Incerpi & [[Robert Sedgewick]], 1985<ref>{{article
  |nom=Incerpi
  |prénom=Janet
  |nom2=Sedgewick
  |prénom2=Robert |lien auteur2=Robert Sedgewick (computer scientist)
  |titre=Improved Upper Bounds on Shellsort
  |journal=Journal of Computer and System Sciences
  |volume=31
  |numéro=2
  |année=1985
  |pages=210–224
  |doi=10.1016/0022-0000(85)90042-x}}</ref>, [[Donald Knuth|Knuth]]<ref name="Knuth">{{ouvrage
  |nom=Knuth
  |prénom=Donald E. |lien auteur=Donald Knuth
  |titre=The Art of Computer Programming. Volume 3: Sorting and Searching
  |édition=2nd
  |éditeur=Addison-Wesley
  |lieu=Reading, Massachusetts
  |année=1997
  |pages=83–95
  |chapitre=Shell's method
  |isbn=0-201-89685-0}}</ref>
|----
| [[OEIS:A036562|A036562]]
| <math>4^k + 3 \cdot 2^{k-1} + 1</math>, préfixé par 1
| <math>1, 8, 23, 77, 281, \ldots</math>
| <math>O\left(N^\frac{4}{3}\right)</math>
| Sedgewick, 1986<ref>
{{ouvrage
  |nom=Sedgewick
  |prénom=Robert
  |lien auteur=Robert Sedgewick (computer scientist)
  |titre=Algorithms in C
  |edition=3rd
  |volume=1
  |éditeur=Addison-Wesley
  |année=1998
  |pages=273–281
  |isbn=0-201-31452-5}}</ref>
|----
| [[OEIS:A033622|A033622]]
| <math>\begin{cases}
  9\left(2^{k} - 2^\frac{k}{2}\right) + 1 & k\text{ pair}, \\
  8 \cdot 2^{k} - 6 \cdot 2^{(k+1)/2} + 1         & k\text{ impair}
\end{cases}</math>
| <math>1, 5, 19, 41, 109, \ldots</math>
| <math>O\left(N^\frac{4}{3}\right)</math>
| Sedgewick, 1986<ref name="Sedgewick2">
  {{article
   |nom=Sedgewick
   |prénom=Robert |lien auteur=Robert Sedgewick (computer scientist)
   |titre=A New Upper Bound for Shellsort
   |journal=Journal of Algorithms
   |volume=7
   |numéro=2
   |année=1986
   |pages=159–173
   |doi=10.1016/0196-6774(86)90001-5
  }}</ref>
|----
|
| <math>h_k = \max\left\{\left\lfloor \frac{5h_{k-1}}{11} \right\rfloor, 1\right\}, h_0 = N</math>
| <math>\left\lfloor \frac{5N}{11} \right\rfloor, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N}{11} \right\rfloor\right\rfloor, \ldots, 1</math>
| Inconnue
| {{Lien|langue=en|fr=Gaston Gonnet}} & {{Lien|langue=en|fr=Ricardo Baeza-Yates}}, 1991<ref name="Gonnet">{{Ouvrage
 |prénom1=Gaston H.
 |nom1=Gonnet
 |prénom2=Ricardo
 |nom2=Baeza-Yates
 |titre=Handbook of Algorithms and Data Structures
 |sous-titre=In Pascal and C
 |éditeur=[[Addison-Wesley]]
 |année=1991
 |numéro d'édition=2
 |pages totales=161–163
 |isbn=0-201-41607-7
 |titre chapitre=Shellsort
 |lieu=Reading, Massachusetts
}}</ref>
|----
| [[OEIS:A108870|A108870]]
| <math>\left\lceil \frac{1}{5} \left(9\cdot \left(\frac{9}{4}\right)^{k-1} - 4 \right) \right\rceil</math>
| <math>1, 4, 9, 20, 46, 103, \ldots</math>
| Inconnue
| Tokuda, 1992<ref>{{ouvrage
  <!--|editor-last=van Leeuven-->
  <!--|editor-first=Jan-->
  |chapter=An Improved Shellsort
  |nom=Tokuda
  |prénom=Naoyuki
  |titre=Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture
  |éditeur=North-Holland Publishing Co.
  |lieu=Amsterdam
  |année=1992
  |pages=449–457
  |isbn=0-444-89747-X}}</ref>
|----
| [[OEIS:A102549|A102549]]
| Inconnue (trouvé expérimentalement)
| <math>1, 4, 10, 23, 57, 132, 301, 701</math><!--Please don't add 1750. It doesn't belong here.-->
| Inconnue
| Ciura, 2001<ref name=":0">{{ouvrage
  |chapter-url=http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf
  |titre=Proceedings of the 13th International Symposium on Fundamentals of Computation Theory
  <!--|editor-last=Freiwalds-->
  <!--|editor-first=Rusins-->
  |nom=Ciura
  |prénom=Marcin
  |chapter=Best Increments for the Average Case of Shellsort
  |éditeur=Springer-Verlag
  |lieu=London
  |année=2001
  |pages=106–117
  |isbn=3-540-42487-3}}</ref>
|}

== Références ==
<references />

== Liens externes ==
{{Autres projets
| wikibooks   = Implémentation_d'algorithmes_classiques/Algorithmes_de_tri/Tri_de_Shell
}}
* [[b:Implémentation d'algorithmes classiques/Algorithmes de tri/Tri de Shell|Shell Sort en C, Java, Pascal, C#]]
* {{en}} [http://www.sorting-algorithms.com/shell-sort Illustration dynamique du tri shell]

{{Palette|Algorithmes de tri}}
{{Portail|informatique théorique}}

{{DEFAULTSORT:Shell, Tri de}}
[[Catégorie:Algorithme de tri]]