Discussion:Tri de Shell
Dernier commentaire : il y a 10 ans par Roll-Morton dans le sujet Complexité minimale
Complexité minimale
modifierLa 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
modifierIl 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.