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	1959
Problèmes liés	Algorithme de tri, algorithme en place, tri par comparaison
Structure des données	liste ou tableau

Complexité en temps

Pire cas	${\displaystyle O(n^{2})}$[2]
Moyenne	${\displaystyle O(n^{1.25})}$[3]
Meilleur cas	${\displaystyle O(n\log n)}$[3]

Complexité en espace

Pire cas	${\displaystyle O(1)}$[3]

modifier - modifier le code - modifier Wikidata

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 juillet 1959 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

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

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 ${\displaystyle 2^{p}3^{q}}$, dans l'ordre croissant, garantissent quant à eux la meilleure complexité théorique prouvée aujourd'hui, ${\displaystyle O(n\log ^{2}n)}$^[6].

Analyse de la 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 ${\displaystyle O\left(n^{2}\right)}$ à ${\displaystyle O\left(n\log ^{2}n\right)}$^[6]. Il est également possible que la complexité en moyenne puisse être ${\displaystyle O\left(n\log n\right)}$ avec un bon choix d'espacements (problème ouvert).

Des bornes inférieures ont aussi été publiées, on peut citer une borne de ${\displaystyle \Omega \left(n\left({\log n \over \log \log n}\right)^{2}\right)}$ 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
	${\displaystyle \left\lfloor {\frac {N}{2^{k}}}\right\rfloor }$	${\displaystyle \left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1}$	${\displaystyle \Theta \left(N^{2}\right)}$ [i.e quand N = 2p]	Donald Shell (en), 1959
	${\displaystyle 2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1}$	${\displaystyle 2\left\lfloor {\frac {N}{4}}\right\rfloor +1,\ldots ,3,1}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Frank & Lazarus, 1960[8]
A168604	${\displaystyle 2^{k}-1}$	${\displaystyle 1,3,7,15,31,63,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Thomas N. Hibbard (en), 1963[9]
A083318	${\displaystyle 2^{k}+1}$, préfixé avec 1	${\displaystyle 1,3,5,9,17,33,65,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Papernov & Stasevich, 1965[10]
A003586	Nombres successifs de la forme ${\displaystyle 2^{p}3^{q}}$ (entier friable 3-lisse)	${\displaystyle 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \Theta \left(N\log ^{2}N\right)}$	Vaughan Ronald Pratt (en), 1971[6]
A003462	${\displaystyle {\frac {3^{k}-1}{2}}}$, plus petit que ${\displaystyle \left\lceil {\frac {N}{3}}\right\rceil }$	${\displaystyle 1,4,13,40,121,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Vaughan Ronald Pratt (en), 1971[6]
A036569	${\displaystyle {\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{où}}\\a_{q}={}&\min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow pgcd(a_{p},n)=1\right\}\\I={}&\left\{0\leq 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{aligned}}}$	${\displaystyle 1,3,7,21,48,112,\ldots }$	${\displaystyle O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)}$	Incerpi & Robert Sedgewick, 1985[11], Knuth[12]
A036562	${\displaystyle 4^{k}+3\cdot 2^{k-1}+1}$, préfixé par 1	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Sedgewick, 1986[13]
A033622	${\displaystyle {\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}}}$	${\displaystyle 1,5,19,41,109,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Sedgewick, 1986[14]
	${\displaystyle h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}}{11}}\right\rfloor ,1\right\},h_{0}=N}$	${\displaystyle \left\lfloor {\frac {5N}{11}}\right\rfloor ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N}{11}}\right\rfloor \right\rfloor ,\ldots ,1}$	Inconnue	Gaston Gonnet (en) & Ricardo Baeza-Yates (en), 1991[15]
A108870	${\displaystyle \left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil }$	${\displaystyle 1,4,9,20,46,103,\ldots }$	Inconnue	Tokuda, 1992[16]
A102549	Inconnue (trouvé expérimentalement)	${\displaystyle 1,4,10,23,57,132,301,701}$	Inconnue	Ciura, 2001[17]