Tri shell

Présentation

Ce tri, proposé en 1959 par Donald L. Shell, constitue une variante optimisée du tri par insertion. Le tri par insertion provoquait le décalage de tous les éléments plus grands que l’élément à insérer. Dans le tri Shell, les éléments ne sont pas décalés d’un élément à la fois, mais de plusieurs éléments, dont la différence d’indice est appelée "pas". Ainsi, à chaque étape, le tri est dégrossit puis le pas est réduit. Chaque réduction de pas provoque un affinage du tri. Lorsque le pas atteint la valeur 1, cela revient à effectuer le tri par insertion. Cependant, cette fois, le tri par insertion est appliqué à un tableau possédant un certain ordre (provoqué par les étapes de préparations où le pas est supérieur à un). En effet, les différentes étapes où le pas est supérieur à un provoque le regroupement des différentes valeurs par groupes de la même taille que le pas. Ainsi par exemple, après une étape où le pas est de quatre, les quatre premières valeurs du tableau sont les quatre plus petites, les quatre suivantes sont plus grandes… En résumé, le tri Shell permet d’organiser plus rapidement le tableau à trier.

Le choix du pas ne doit pas s’effectuer n’importe comment. En effet, les valeurs des différents pas successifs ne doivent pas, pour des raisons de plus grande efficacité, être multiples des autres et il faut absolument réaliser l’étape ou le pas est égal à un. La formule la plus couramment utilisée pour calculer la valeur des pas successifs est la suivante U(n+1)=(3Un+1) avec U0=0.

Soit n le nombre d’éléments du tableau et p le pas, le pas doit être tel que p

Grandeurs successives de p pour n=100

Calcul du plus grande valeur de p tel que p<100 :
 U0=0
 U1=3U0+1=1
 U2=3U1+1=4
 U3=3U2+1=13
 U4=3U3+1=40
 U5=3U4+1=121

Conclusion : la plus grande valeur de p tel que p<100 est 40. Les valeurs successives du pas p seront alors : (ou la division par 3 est une division entiére).
 p1=121/3=40
 p2=p1/3=40/3=13
 p3=p2/3=13/3=4
 p4=p3/3=4/3=1

Exemple de tri

Évolution du tableau au fil du tri shell. Le pas, représenté en rouge est également indiqué ainsi que la valeur en mémoire, sur laquelle porte la comparaison. En bleu, les valeurs sur lesquels portent les comparaisons à chaque étape.

A ce stade, le tri fusion revient à effectuer le tri par insertion. L’exemple s’arrêtera donc ici. Il faut cependant remarquer que, grâce aux différentes étapes du tri Shell, le tableau est un peu mieux organisé : La moyenne des valeurs de la première moitié du tableau a diminué. Ce résultat est d’autant plus remarquable que le tableau à trier est grand.

Complexité

La complexité de ce tri est encore une fois en O(n²). L’algorithme de tri Shell est cependant généralement plus rapide et efficace que le tri par insertion (quelques exception existent malgré tout mais ce sont des cas très particuliers). Le calcul exact de la complexité en nombre de comparaisons de ce tri ne sera pas traité ici car ce calcul est assez complexe et sans grand intérêt puisque le tri Shell n’est qu’une optimisation assez géniale du tri par insertion.

 Accueil des algorithmes de tri
 Article précédent : le tri par insertion
 Article suivant : le tri fusion