Aide & Téléchargement

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)=(3U_n+1) avec U₀=0.

Soit n le nombre d'éléments du tableau et p le pas, le pas doit être tel que p<n. Certains algorithmes imposent la taille des pas successifs, qui sont, par exemple, écrits en dur au sein du programme. L'inconvénient est que le nombre de valeurs à trier peut être bien supérieur au plus grand pas prévu par la personne ayant implémenté l'algorithme. La version qui est proposée ici préfère calculer, à l'aide de la formule donnée ci-dessus, le plus grand pas p tel que p<n. Pour trouver les autres valeurs successives de p, il suffit, à chaque étape, de diviser p par 3 (division entière).

Exemple 1 : 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 2: tri

Evolution 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.

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

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.

Pseudo langage
C / C++		Caml		Java		OCaml

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.