Une introduction à l’algorithme de tri Shell
Le tri Shell est une technique de tri qui divise une liste donnée en sous-listes, puis les trie à l'aide du tri par insertion. L'algorithme utilise un écart n qui choisit des éléments espacés de n pour comprendre les sous-listes.
Les sous-listes sont ensuite triées à l'aide du tri par insertion, après quoi elles sont combinées. La liste combinée n'est pas entièrement triée mais donne à l'algorithme l'avantage de rapprocher les éléments de leur position finale.
Le tri par insertion est à nouveau utilisé pour finalement trier la liste.
Un examen plus approfondi du tri des coquilles
La description ci-dessus n'avait peut-être pas beaucoup de sens, mais un exemple devrait vous aider. Supposons que vous ayez la liste : [39, 6, 2, 51, 30, 42, 7, 4, 16] et une valeur d'écart de trois.
La première sous-liste aurait des éléments : 39, 51, 7
La deuxième sous-liste : 6, 30, 4
La troisième et dernière sous-liste : 2, 42, 16
Après le tri par insertion, chacune des sous-listes serait ordonnée comme suit :
Le premier : 7, 39, 51
La seconde : 4, 6, 30
Le troisième : 2, 16, 42
La sous-liste triée est maintenant combinée d'une manière particulière. Chaque élément de sous-liste est placé dans l'index à partir duquel la valeur de sous-liste non triée d'origine a été rassemblée.
Vous allez donc vous retrouver avec la séquence ci-dessous :
[7, 4, 2, 39, 6, 16, 51, 30, 42]
Notez que la liste n'est toujours pas triée mais que les éléments sont plus proches des positions dans lesquelles ils sont censés se trouver. Après avoir effectué le tri par insertion sur cette combinaison de listes, la liste sera finalement triée :
[2, 4, 6, 7, 16, 30, 39, 42, 51]
Analyse d'algorithmes
La complexité du tri shell est comprise entre O(n) et O(n2). Le calcul de cette conclusion dépasse le cadre de cet article.
Implémentation Python :
def shellSort(my_list):
n = len(my_list)
interval = n // 2 # floor division
while interval > 0:
for val in range(interval, n):
temp = my_list[val]
x = val
while x >= interval and my_list[x - interval] > temp:
my_list[x] = my_list[x - interval]
x = x - interval
my_list[x] = temp
interval = interval // 2Passer au tri par fusion
Il existe plusieurs algorithmes de tri, chacun avec un fonctionnement unique. Le tri par fusion, par exemple, utilise une stratégie de division pour régner et a une complexité de O(nlogn).
Le tri par fusion est, dans certains cas, meilleur que le tri par shell et vaut vraiment la peine d'être examiné. Il devrait être le prochain sur votre liste de lecture d'algorithmes de tri.