Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Tri de Shell
Résumé
vignette|Tri de Shell barres de couleur de l'algorithme
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.
Le nom vient de son inventeur (1924-2015) qui publia l'algorithme dans le numéro de de Communications of the ACM.
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).
tab = [701, 301, 132, 57, 23, 10, 4, 1]
def shell_sort(tab):
n = len(tab)
for m in tab:
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 Les premiers espacements optimaux (empiriquement trouvés) sont les suivants : 1, 4, 10, 23, 57, 132, 301, 701. 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 gapSource officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.