Parmi les nombreuses méthodes de tri développées en informatique, le tri Shell-Metzner, plus connu aujourd'hui sous le nom de tri de Shell (Shell Sort), occupe une place particulière en raison de son approche ingénieuse visant à réduire le nombre de comparaisons et de permutations nécessaires pour ordonner un tableau. Cet algorithme a été conçu pour améliorer les performances des méthodes de tri simples, notamment celles reposant sur des comparaisons successives d'éléments adjacents. Son principe fondamental consiste à ne pas comparer uniquement des éléments voisins, mais plutôt des éléments séparés par un certain intervalle, appelé écart ou gap. Cette stratégie permet de déplacer rapidement les valeurs très éloignées de leur position finale et de rapprocher progressivement le tableau d'un état déjà partiellement trié. Ainsi, lorsque les comparaisons finales entre éléments adjacents sont effectuées, une grande partie du travail a déjà été accomplie, ce qui réduit considérablement le nombre total d'opérations nécessaires.

Le fonctionnement de cet algorithme est relativement simple à comprendre. Au départ, l'écart utilisé correspond généralement à la moitié de la taille du tableau. Les éléments situés à cette distance sont alors comparés et échangés lorsqu'ils ne sont pas dans le bon ordre. Une fois ce premier passage terminé, l'écart est réduit, souvent en étant divisé par deux, et le processus est répété. Les comparaisons sont ainsi réalisées avec des intervalles de plus en plus petits jusqu'à ce que l'écart atteigne finalement la valeur 1. À ce stade, le tableau est déjà largement ordonné et les dernières comparaisons permettent d'obtenir un tri complet avec beaucoup moins d'efforts qu'un tri élémentaire classique. Le programme QuickBASIC présenté ci-dessous met en oeuvre cette technique sur un tableau de nombres entiers. Avant le traitement, les valeurs sont affichées dans leur ordre initial, puis l'algorithme applique successivement les différentes phases de tri en réduisant progressivement l'écart utilisé. Une fois le processus terminé, le tableau est affiché de nouveau afin de montrer le résultat final. Cet exemple illustre parfaitement comment une idée relativement simple permet d'obtenir un algorithme nettement plus efficace que plusieurs méthodes de tri pédagogiques, tout en conservant une implémentation compacte et facile à comprendre. Pour cette raison, le tri Shell-Metzner demeure un classique de l'algorithmique et une excellente introduction aux techniques d'optimisation des opérations de tri.

Vous trouverez la réponse que vous souhaitez, à l'aide du code source QuickBASIC suivant :

on obtiendra le résultat suivant :

Voir également

Algorithme - Tri