Coquillage - Shellsort

Coquillage

Shellsort avec interstices 23, 10, 4, 1 en action
Classer	Algorithme de tri
Structure de données	Déployer
Performances dans le pire des cas	O( n 2 ) (la plus mauvaise séquence d'espacement connue dans le pire des cas) O( n log 2 n ) (la plus mauvaise séquence d'espacement connue dans le pire des cas)
Le meilleur cas la performance	O( n log n ) (la plupart des séquences de lacunes) O( n log 2 n ) (la plus mauvaise séquence de lacunes connue)
Performances moyennes	dépend de la séquence d'espacement
Complexité spatiale dans le pire des cas	О( n ) total, O(1) auxiliaire

Échanger des paires d'articles dans les étapes successives de Shellsort avec les écarts 5, 3, 1

Shellsort , également connu sous le nom de Shell sort ou méthode de Shell , est un tri par comparaison sur place . Il peut être vu comme étant soit une généralisation du tri par échange ( tri à bulles ) ou le tri par insertion ( tri par insertion ). La méthode commence par trier des paires d'éléments très éloignées les unes des autres, puis réduit progressivement l'écart entre les éléments à comparer. En commençant par des éléments éloignés, il peut déplacer certains éléments déplacés en position plus rapidement qu'un simple échange de voisins les plus proches. Donald Shell a publié la première version de ce type en 1959. Le temps d'exécution de Shellsort dépend fortement de la séquence d'intervalles qu'il utilise. Pour de nombreuses variantes pratiques, la détermination de leur complexité temporelle reste un problème ouvert .

La description

Shellsort est une optimisation du tri par insertion qui permet l'échange d'éléments éloignés les uns des autres. L'idée est d'arranger la liste des éléments de sorte que, en commençant n'importe où, en prenant chaque h ième élément, on produise une liste triée. Une telle liste est dite h- triée. Il peut également être considéré comme h listes entrelacée, toutes triées individuellement. Commencer par de grandes valeurs de h permet aux éléments de se déplacer sur de longues distances dans la liste d'origine, ce qui réduit rapidement de grandes quantités de désordre et laisse moins de travail pour les étapes de tri h plus petites . Si la liste est ensuite triée en k pour un entier plus petit k , alors la liste reste triée en h . Suivre cette idée pour une séquence décroissante de valeurs h se terminant par 1 est garanti pour laisser une liste triée à la fin.

En termes simplistes, cela signifie que si nous avons un tableau de 1024 nombres, notre premier écart ( h ) pourrait être 512. Nous parcourons ensuite la liste en comparant chaque élément de la première moitié à l'élément de la seconde moitié. Notre deuxième écart ( k ) est de 256, ce qui divise le tableau en quatre sections (à partir de 0,256,512,768), et nous nous assurons que les premiers éléments de chaque section sont triés les uns par rapport aux autres, puis le deuxième élément de chaque section, et ainsi de suite . En pratique, la séquence d'écarts peut être n'importe quoi, mais le dernier écart est toujours 1 pour terminer le tri (finissant effectivement avec un tri par insertion ordinaire).

Un exemple d'exécution de Shellsort avec les écarts 5, 3 et 1 est présenté ci-dessous.

La première passe, 5-tri, effectue un tri par insertion sur cinq sous-tableaux distincts ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( un ₅ , un ₁₀ ). Par exemple, il change le sous-tableau ( a ₁ , a ₆ , a ₁₁ ) de (62, 17, 25) à (17, 25, 62). La passe suivante, 3-tri, effectue un tri par insertion sur les trois sous-tableaux ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , un ₉ , un ₁₂ ). La dernière passe, 1-tri, est un tri par insertion ordinaire de l'ensemble du tableau ( a ₁ ,..., a ₁₂ ).

Comme l'illustre l'exemple, les sous-tableaux sur lesquels Shellsort opère sont initialement courts ; plus tard, ils sont plus longs mais presque commandés. Dans les deux cas, le tri par insertion fonctionne efficacement.

Shellsort n'est pas stable : il peut changer l'ordre relatif des éléments de valeurs égales. Il s'agit d'un algorithme de tri adaptatif dans la mesure où il s'exécute plus rapidement lorsque l'entrée est partiellement triée.

Pseudocode

Utilisation de la séquence d'espacement de Marcin Ciura, avec un tri par insertion interne.

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]  // Ciura gap sequence

# Start with the largest gap and work down to a gap of 1
foreach (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

Séquences d'espacement

La question de décider quelle séquence d'espacement utiliser est difficile. Chaque séquence d'espaces contenant 1 donne un tri correct (car cela fait de la passe finale un tri par insertion ordinaire) ; cependant, les propriétés des versions ainsi obtenues de Shellsort peuvent être très différentes. Trop peu d'écarts ralentissent les passes, et trop d'écarts produisent un surcoût.

Le tableau ci-dessous compare la plupart des séquences de lacunes proposées publiées à ce jour. Certains d'entre eux ont des éléments décroissants qui dépendent de la taille du tableau trié ( N ). D'autres sont des séquences infinies croissantes, dont les éléments inférieurs à N doivent être utilisés dans l'ordre inverse.

OEIS	Terme général ( k ≥ 1)	Lacunes en béton	Complexité temporelle 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)}$[par exemple quand N = 2 p ]	Coquille , 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 & Lazare, 1960
A000225	${\style d'affichage 2^{k}-1}$	${\displaystyle 1,3,7,15,31,63,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Hibbard , 1963
A083318	${\style d'affichage 2^{k}+1}$, préfixé par 1	${\displaystyle 1,3,5,9,17,33,65,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Papernov & Stasevitch, 1965
A003586	Chiffres successifs de la forme ( 3- chiffres lisses ) ${\displaystyle 2^{p}3^{q}}$	${\style d'affichage 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \Theta \left(N\log ^{2}N\right)}$	Pratt , 1971
A003462	${\displaystyle {\frac {3^{k}-1}{2}}}$, pas plus de ${\displaystyle \left\lceil {\frac {N}{3}}\right\rceil }$	${\displaystyle 1,4,13,40,121,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Knuth , 1973, d'après Pratt , 1971
A036569	${\displaystyle {\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{where}}\\a_{0}={}&3\\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 \gcd(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{aligné}}}$	${\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 & Sedgewick , 1985, Knuth
A036562	${\displaystyle 4^{k}+3\cdot 2^{k-1}+1}$, préfixé par 1	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle O\gauche(N^{\frac {4}{3}}\droite)}$	Sedgewick, 1982
A033622	${\displaystyle {\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{ even}},\\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\gauche(N^{\frac {4}{3}}\droite)}$	Sedgewick, 1986
	${\displaystyle h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0} =N}$	${\displaystyle \left\lfloor {\frac {5N-1}{11}}\right\rfloor ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N-1} {11}}\right\rfloor -1\right\rfloor ,\ldots ,1}$	Inconnu	Gonnet & Baeza-Yates , 1991
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 }$	Inconnu	Tokuda, 1992
A102549	Inconnu (dérivé expérimentalement)	${\style d'affichage 1,4,10,23,57,132,301,701}$	Inconnu	Ciura, 2001

Lorsque la représentation binaire de N contient de nombreux zéros consécutifs, Shellsort utilisant la séquence d'écarts d'origine de Shell effectue des comparaisons Θ( N ² ) dans le pire des cas. Par exemple, ce cas se produit pour N égal à une puissance de deux lorsque des éléments plus grands et plus petits que la médiane occupent respectivement des positions impaires et paires, puisqu'ils ne sont comparés qu'à la dernière passe.

Bien qu'il ait une complexité plus élevée que le O ( N  log  N ) qui est optimal pour les tris de comparaison, la version de Pratt se prête aux réseaux de tri et a la même complexité de porte asymptotique que le trieur bitonique de Batcher .

Gonnet et Baeza-Yates ont observé que Shellsort fait le moins de comparaisons en moyenne lorsque les ratios d'écarts successifs sont à peu près égaux à 2,2. C'est pourquoi leur séquence de ratio 2,2 et la séquence de Tokuda de ratio 2,25 s'avèrent efficaces. Cependant, on ne sait pas pourquoi il en est ainsi. Sedgewick recommande d'utiliser des espaces qui ont des plus grands diviseurs communs faibles ou qui sont deux à deux premiers entre eux .

En ce qui concerne le nombre moyen de comparaisons, la séquence de Ciura a les performances les plus connues ; les écarts de 701 n'ont pas été déterminés mais la séquence peut être encore étendue selon la formule récursive . ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

La séquence de Tokuda, définie par la formule simple , où , , peut être recommandée pour des applications pratiques. ${\displaystyle h_{k}=\lceil h'_{k}\rceil }$${\displaystyle h'_{k}=2.25h'_{k-1}+1}$${\displaystyle h'_{1}=1}$

Si la taille d'entrée maximale est petite, comme cela peut se produire si Shellsort est utilisé sur de petits sous-tableaux par un autre algorithme de tri récursif tel que quicksort ou merge sort , il est alors possible de tabuler une séquence optimale pour chaque taille d'entrée.

Complexité de calcul

La propriété suivante est vérifiée : après le tri en h ₂ de tout tableau trié en h ₁ , le tableau reste trié en h ₁ . Chaque tableau trié en h ₁ et trié en h ₂ est également trié ( a ₁ h ₁ + a ₂ h ₂ ), pour tout entier non négatif a ₁ et a ₂ . La complexité au pire des cas de Shellsort est donc liée au problème de Frobenius : pour des entiers donnés h ₁ ,..., h _n avec pgcd = 1, le nombre de Frobenius g ( h ₁ ,..., h _n ) est le plus grand entier qui ne peut pas être représenté par un ₁ h ₁ + ... + a _n h _n avec un entier non négatif a ₁ ,..., a _n . En utilisant des formules connues pour les nombres de Frobenius, nous pouvons déterminer la complexité dans le pire des cas de Shellsort pour plusieurs classes de séquences de lacunes. Les résultats prouvés sont indiqués dans le tableau ci-dessus.

En ce qui concerne le nombre moyen d'opérations, aucun des résultats prouvés ne concerne une séquence d'intervalles pratique. Pour les écarts qui sont des puissances de deux, Espelid a calculé cette moyenne comme . Knuth a déterminé que la complexité moyenne du tri d'un tableau à N éléments avec deux écarts ( h , 1) était . Il s'ensuit qu'un Shellsort à deux passes avec h = ( N ^1/3 ) fait en moyenne O ( N ^5/3 ) comparaisons/inversions/temps d'exécution. Yao a trouvé la complexité moyenne d'un Shellsort à trois passes. Son résultat a été affiné par Janson et Knuth : le nombre moyen de comparaisons/inversions/temps d'exécution effectué lors d'un Shellsort à trois écarts ( ch , cg , 1), où h et g sont premiers entre eux, est dans la première passe, dans la seconde passe et dans la troisième passe. ψ ( h , g ) dans la dernière formule est une fonction complexe égale à asymptotiquement . En particulier, lorsque h = ( N ^7/15 ) et g = Θ( N ^1/5 ), le temps moyen de tri est O ( N ^23/15 ). ${\displaystyle 0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)}$${\displaystyle {\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}}$${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)}$${\displaystyle \psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O \gauche((c-1)gh^{1/2}N\droite)+O\gauche(c^{2}g^{3}h^{2}\droite)}$${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^ {-1/2}\droit)}$

Sur la base d'expériences, on suppose que Shellsort avec la séquence de lacunes de Hibbard s'exécute en un temps moyen de O ( N ^5/4 ), et que la séquence de Gonnet et Baeza-Yates nécessite en moyenne 0,41 N  ln  N  (ln ln  N  + 1/6 ) l'élément se déplace. Les approximations du nombre moyen d'opérations précédemment proposées pour d'autres séquences échouent lorsque les tableaux triés contiennent des millions d'éléments.

Le graphique ci-dessous montre le nombre moyen de comparaisons d'éléments dans diverses variantes de Shellsort, divisé par la limite inférieure théorique, c'est-à-dire log ₂ N !, où la séquence 1, 4, 10, 23, 57, 132, 301, 701 a été étendue selon la formule . ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

En appliquant la théorie de la complexité de Kolmogorov , Jiang, Li et Vitányi ont prouvé la borne inférieure suivante pour l'ordre du nombre moyen d'opérations/durée d'exécution dans un Shellsort p -pass : Ω( pN ^{1+1/ p} ) lorsque p  ≤ log ₂ N et ( pN ) lorsque p  > log ₂ N . Par conséquent, Shellsort a des perspectives de fonctionner dans un temps moyen qui augmente asymptotiquement comme N log N uniquement lors de l'utilisation de séquences d'espaces dont le nombre d'espaces augmente proportionnellement au logarithme de la taille du tableau. On ne sait cependant pas si Shellsort peut atteindre cet ordre asymptotique de complexité moyenne des cas, qui est optimal pour les tris par comparaison. La limite inférieure a été améliorée par Vitányi pour chaque nombre de passes à où . Ce résultat implique par exemple la borne inférieure de Jiang-Li-Vitányi pour toutes les séquences d'incréments de passage et améliore cette borne inférieure pour des séquences d'incréments particulières. En fait, toutes les bornes (inférieure et supérieure) actuellement connues pour le cas moyen correspondent précisément à cette borne inférieure. Par exemple, cela donne le nouveau résultat que la limite supérieure de Janson-Knuth correspond à la limite inférieure résultante pour la séquence d'incréments utilisée, montrant que Shellsort à trois passes pour cette séquence d'incréments utilise des comparaisons/inversions/temps d'exécution. La formule nous permet de rechercher des séquences d'incréments qui donnent des limites inférieures inconnues ; par exemple une séquence d'incréments pour quatre passes dont la borne inférieure est supérieure à celle de la séquence d'incréments . La borne inférieure devient ${\style d'affichage p}$${\displaystyle \Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})}$${\displaystyle h_{0}=N}$${\style d'affichage p}$${\displaystyle \Thêta (N^{23/15})}$${\displaystyle \Omega (pn^{1+1/p})=\Omega (n^{5/4})}$${\displaystyle h_{1}=n^{11/16},}$ ${\displaystyle h_{2}=n^{7/16},}$ ${\displaystyle h_{3}=n^{3/16},}$ ${\style d'affichage h_{4}=1}$${\displaystyle T=\Omega (n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3 /16})=\Oméga (n^{1+5/16})=\Oméga (n^{21/16}).}$

La complexité dans le pire des cas de n'importe quelle version de Shellsort est d'un ordre supérieur : Plaxton, Poonen et Suel ont montré qu'elle croît au moins aussi rapidement que . ${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$

Applications

Shellsort effectue plus d'opérations et a un taux d' échec de cache plus élevé que quicksort . Cependant, comme elle peut être implémentée en utilisant peu de code et n'utilise pas la pile d'appels , certaines implémentations de la fonction qsort dans la bibliothèque standard C destinée aux systèmes embarqués l' utilisent à la place de quicksort. Shellsort est, par exemple, utilisé dans la bibliothèque uClibc . Pour des raisons similaires, dans le passé, Shellsort était utilisé dans le noyau Linux .

Shellsort peut également servir de sous-algorithme de tri introspectif , pour trier des sous-tableaux courts et éviter un ralentissement lorsque la profondeur de récursivité dépasse une limite donnée. Ce principe est utilisé, par exemple, dans le compresseur bzip2 .

Voir également

• Tri en peigne

Les références

Bibliographie

• Knuth, Donald E. (1997). "Méthode de Shell". L'art de la programmation informatique. Volume 3 : Tri et recherche (2e éd.). Reading, Massachusetts : Addison-Wesley. p. 83-95. ISBN 978-0-201-89685-5.
• Analysis of Shellsort and Related Algorithms , Robert Sedgewick, Quatrième Symposium européen sur les algorithmes, Barcelone, septembre 1996.

Liens externes

• Algorithmes de tri animés : Shell Sort at the Wayback Machine (archivé le 10 mars 2015) – démonstration graphique
• Shellsort avec des lacunes 5, 3, 1 comme une danse folklorique hongroise