Shellsort

_{La propriété suivante} est vérifiée : après un tri h₂ d'un tableau trié h₁, ce tableau reste trié h₁. [21] Tout tableau trié h₁ et h₂ est également trié (a₁h₁ ₊ a₂h₂ ) _, pour tous _entiers non négatifs . La complexité dans le pire des cas de _{Shellsort est} donc _liée au _{problème de} Frobenius : pour des entiers h₁, ..., hₙ donnés, de PGCD = ₁ , le nombre de Frobenius g(h₁ , ... , _hₙ ) est le plus grand entier qui ne peut être représenté sous la forme _{a₁h₁ + ... + aₙhₙ, avec des entiers non négatifs a₁, ..., aₙ} . _À l' aide des formules _connues pour les _{nombres de} Frobenius , _{on peut déterminer la complexité dans le pire des} cas de Shellsort pour plusieurs classes de séquences à intervalles. Les résultats obtenus sont présentés dans le tableau ci-dessus .

Mark Allen Weiss a prouvé que Shellsort s'exécute en O ( N log N ) temps lorsque le tableau d'entrée est en ordre inverse.

Concernant le nombre moyen d'opérations, aucun des résultats démontrés ne concerne une séquence d'intervalles pratique. Pour des intervalles qui sont des puissances de deux, Espelid a calculé cette moyenne comme suit : Knuth a déterminé que la complexité moyenne du tri d'un tableau de N éléments avec deux intervalles ( h , 1) est de : . Il s'ensuit qu'un tri Shell en deux passes avec h = Θ( N ^{^1/3} ) effectue en moyenne O ( N ^{^5/3} ) comparaisons/inversions/temps d'exécution. Yao a trouvé la complexité moyenne d'un tri Shell en trois passes. Son résultat a été affiné par Janson et Knuth : le nombre moyen de comparaisons/inversions/temps d'exécution effectués lors d'un tri Shell avec trois intervalles ( ch , cg , 1), où h et g sont premiers entre eux, est de : lors de la première passe, lors de la deuxième passe et lors de la troisième passe. ψ ( h , g ) dans la dernière formule est une fonction complexe asymptotiquement égale à . En particulier, lorsque h = Θ( N ^7/15 ) et g = Θ( N ^1/5 ), le temps moyen de tri est O ( N ^23/15 ).

D'après des expériences, on suppose que l'algorithme Shellsort avec la séquence d'espacement de Hibbard s'exécute en temps moyen O ( N⁵ ^{/⁴ )} , et que la séquence de Gonnet et Baeza-Yates nécessite en moyenne 0,41 N ln N (ln ln N + 1/6) déplacements d'éléments . Les approximations du nombre moyen d'opérations proposées précédemment pour d'autres séquences deviennent inapplicables lorsque les tableaux triés contiennent des millions d'éléments.

Le graphique ci-dessous montre le nombre moyen de comparaisons d'éléments utilisées par diverses séquences d'intervalles, divisé par la limite inférieure théorique , c'est-à-dire log ₂ N !. La séquence de Ciuria 1, 4, 10, 23, 57, 132, 301, 701 (étiquetée Ci01) a été étendue selon la formule .

En appliquant la théorie de la complexité de Kolmogorov , Jiang, Li et Vitányi ont démontré la borne inférieure suivante pour l'ordre du nombre moyen d'opérations par temps d'exécution dans un tri Shell à p passes : Ω( pN ₎ ^{= 1 + 1/} p ^lorsque p ≤ log₂N et Ω( pN ) lorsque p > log₂N . Par conséquent, le tri Shell a la possibilité de s'exécuter en un temps moyen qui croît asymptotiquement comme _N log N uniquement lorsqu'on utilise des séquences d'intervalles dont le nombre d'intervalles croît proportionnellement au logarithme de la taille du tableau. On ignore cependant si le tri Shell peut atteindre cet ordre asymptotique de complexité en moyenne, qui est optimal pour les tris par comparaison. Vitányi a amélioré cette borne inférieure pour tout nombre de passes, en l' établissant à Ω(pN) = 1. Ce résultat implique par exemple la borne inférieure de Jiang-Li-Vitányi pour toutes les séquences d'incréments à p passes et améliore cette borne inférieure pour des séquences d'incréments particulières. En fait, toutes les bornes (inférieures et supérieures) actuellement connues pour le cas moyen sont précisément égales à cette borne inférieure. Par exemple, cela donne le nouveau résultat que la borne supérieure de Janson-Knuth est égale à la borne inférieure résultante pour la séquence d'incréments utilisée, montrant que le tri Shell à trois passes pour cette séquence d'incréments utilise un temps d'exécution de comparaisons/inversions. La formule nous permet de rechercher des séquences d'incréments qui donnent des bornes 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 alors

La complexité dans le pire des cas de toute version de Shellsort est d'ordre supérieur : Plaxton, Poonen et Suel ont montré qu'elle croît au moins aussi rapidement que . Robert Cypher a prouvé une borne inférieure plus forte : lorsque pour tout . h_s" $h\_\{s{h}_{s+1}>h_s$h_{s

Shellsort effectue davantage d'opérations et présente un taux d'échecs de cache plus élevé que quicksort . Cependant, comme il peut être implémenté avec peu de code et n'utilise pas la pile d'appels , certaines implémentations de la fonction qsort de la bibliothèque standard C destinées 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, Shellsort était auparavant 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écursion dépasse une limite donnée. Ce principe est employé, par exemple, dans le compresseur bzip2 .