L'amélioration proposée par le tri à insertion dans les
2 sens n'apporte aucun remède au problème des mouvements des
éléments. Pour diminuer ce nombre, il serait préférable
de faire faire des grands bonds aux éléments plutôt que de
les déplacer d'une place à la fois. Donald L.Shell a proposé
en 1959 d'effectuer le tri en plusieurs étapes avec des éléments
non contigus et de moins en moins espacés.
Dans l'exemple ci-dessous, on a choisi successivement 4, 2 et 1 comme distances
séparant les éléments à trier à chaque
étape et on obtient:
le vecteur à trier est:
1
2
3
4
5
6
7
8
9
6
5
4
9
1
7
8
3
2
Indiquons le éléments à trier en rouge (de numéros 1, 5 et 9 distants de 4)
1
2
3
4
5
6
7
8
9
6
5
4
9
1
7
8
3
2
On obtient
1
2
3
4
5
6
7
8
9
1
5
4
9
2
7
8
3
6
Il faut maintenant trier les éléments de numéro 2 et 6 (toujours distants de 4)
1
2
3
4
5
6
7
8
9
1
5
4
9
2
7
8
3
6
On obtient
1
2
3
4
5
6
7
8
9
1
5
4
9
2
7
8
3
6
Il faut maintenant trier les éléments de numéro 3 et 7 (toujours distants de 4)
1
2
3
4
5
6
7
8
9
1
5
4
9
2
7
8
3
6
On obtient
1
2
3
4
5
6
7
8
9
1
5
4
9
2
7
8
3
6
Il faut maintenant trier les éléments de numéro 4 et 8
1
2
3
4
5
6
7
8
9
1
5
4
9
2
7
8
3
6
On obtient
1
2
3
4
5
6
7
8
9
1
5
4
3
2
7
8
9
6
Il faut maintenant trier les éléments de numéro 5 et 9
1
2
3
4
5
6
7
8
9
1
5
4
9
2
7
8
3
6
On obtient
1
2
3
4
5
6
7
8
9
1
5
4
3
2
7
8
9
6
Dans une deuxième phase, on va trier les éléments dont les numéros ont un écart
de 2: 1, 3, 5, 7, 9
1
2
3
4
5
6
7
8
9
1
5
4
3
2
7
8
9
6
On obtient
1
2
3
4
5
6
7
8
9
1
5
2
3
4
7
6
9
8
Ceux de numéros 2, 4, 6, 8
1
2
3
4
5
6
7
8
9
1
5
2
3
4
7
6
9
8
On obtient
1
2
3
4
5
6
7
8
9
1
3
2
5
4
7
6
9
8
Dans une troisième phase, on va trier les éléments dont les numéros ont un
écart de 1, à savoir 1, 2, 3, ..., 9
On obtient
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
Note: Dans la pratique, on choisit souvent ..., 10, 7, 4, 1 comme écarts entre les
éléments à trier à chaque étape.
Et Donald Knuth suggère lui de choisir comme écart:
h1=1
hs+1=3*hs+1 pour s>1
et de prendre ht tel que ht+2>=N