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 Calcul du plus grande valeur de p tel que p<100 :
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).
É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. La complexité de ce tri est encore une fois en O(n2). 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.Grandeurs successives de p pour n=100
U0=0
U1=3U0+1=1
U2=3U1+1=4
U3=3U2+1=13
U4=3U3+1=40
U5=3U4+1=121
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
Tableau Memoire Pas Commentaire 6 3 0 9 1 7 8 2 5 4 t(4)=1 4 Comparaison de memoire=t(4) avec t(0) : t(4) reçoit t(0) puis t(0) reçoit memoire 1 3 0 9 6 7 8 2 5 4 t(5)=7 4 Comparaison de memoire=t(5) avec t(1) : pas d'échange 1 3 0 9 6 7 8 2 5 4 t(6)=8 4 Comparaison de memoire=t(6) avec t(2) : pas d'échange 1 3 0 9 6 7 8 2 5 4 t(7)=9 4 Comparaison de memoire=t(7) avec t(3) : t(7) reçoit t(3) puis t(3) reçoit memoire 1 3 0 2 6 7 8 9 5 4 t(8)=5 4 Comparaison de memoire=t(8) avec t(4) : t(8) reçoit t(4) 1 3 0 2 6 7 8 9 6 4 t(8)=5 4 Comparaison de memoire avec t(0) : pas d'échange t(4) reçoit memoire 1 3 0 2 5 7 8 9 6 4 t(9)=4 4 Comparaison de memoire=t(9) avec t(5) : t(9) reçoit t(5) 1 3 0 2 5 7 8 9 6 7 4 4 Comparaison de memoire avec t(1) : pas d'échange, t(5) reçoit memoire 1 3 0 2 5 4 8 9 6 7 4 1 A ce stade, le pas diminue 4/3 donne un pas de 1
Pseudo langage
C / C++
Caml
Java
OCaml
Complexité
Accueil des algorithmes de tri
Article précédent : le tri par insertion
Article suivant : le tri fusion