Discussion:Tri de Shell
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Faible |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article comporte une liste de tâches suggérées :
modifier • suivre • rafraîchir • aide
Votre aide est la bienvenue pour corriger les arguments inconnus dans les appels de modèle, présents dans l'article :
- Modèle {{ Ouvrage }} : l'argument «
chapter-url=http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf↵» ne fait pas partie des arguments gérés par le modèle {{ Ouvrage }} (dans « Complexité ») -- 10 novembre 2021 à 10:35 (CET)
- Modèle {{ Ouvrage }} : l'argument «
Complexité minimale[modifier le code]
La complexité minimale semble être Source sur wikipédia anglais Theo77186 (discuter) 29 juillet 2014 à 21:24 (CEST)
- Voilà, j'ai rajouté l'info et la sources. --Roll-Morton (discuter) 1 août 2014 à 13:52 (CEST)
Le pseudo code est faux[modifier le code]
Il faut 4 boucles imbriquées:
- boucle sur les gaps
- boucle sur le modulo m du gap (offset)
- boucle sur les entiers de la forme k * gap + m
- boucle en arrière pour faire l'insertion.
Cf la version anglaise.
Avec un pseudo code en python (ou autre) que l'on peut tester, cela serait mieux ?
Voici un code correct en 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 = t[i]
while j > r and t[j-m] > x:
t[j] = t[j-m]
j = j - m
t[j] = x
J'ai corrigé la page.