Tri Shell
Principe
Cet algorithme a été créé par Donald.L. Shell, d'où son nom.
Il est fondé sur le constat que le tri par insertion est très performant sur un tableau presque trié.
Contrairement au tri par insertion, l'algorithme de tri Shell n'effectue pas le tri du tableau en une seule passe.
- Le tableau est partagé en segments disjoints, dont chacun est trié selon un tri par insertion.
Chaque segment est constitué de cases situées à une certaine distance les unes des autres ; par exemple, si la distance est 3, un segment sera constitué des cases (1, 4, 7, 10, ...), un autre segment des cases (2, 5, 8, 11, ...), etc ...
- Lorsque tous les segments ont été triés individuellement, le tableau est de nouveau partagé, mais en un moins grand nombre de segments.
- Le processus est répété jusqu'à ce que le nombre de segments soit de 1.
Algorithme
Déterminer la liste des distances à utiliser Pour Distance variant de DistanceMax à 1
Pour IDebut variant de (Distance + IMin) à IMax
- Valeur_A_Classer = Tableau(IDebut)
- IInsere = IDebut
- Tant que Tableau(IInsere - Distance) > Valeur_A_Classer et IInsere >= (Distance + IMin)
- Tableau(IInsere) = Tableau(IInsere - Distance)
- IInsere = IInsere - Distance
- Tableau(IInsere) = Valeur_A_Classer
Exemple
Tableau à trier : [7,5,1,9,2]
L'évolution du tableau est figurée ci-dessous
Les éléments colorés sont ceux qui constituent le sous-tableau en cours de tri.
Les éléments en gras sont ceux comparés dans le tri par insertion : la valeur est mémorisée dans la dernière colonne, comme dans le cas du tri par insertion
| 1 |
2 |
3 |
4 |
5 |
|
Valeur |
|
1 |
2 |
3 |
4 |
5 |
|
Valeur |
| Distance = 3 |
Distance = 1 |
| 7 |
5 |
1 |
9 |
2 |
|
9 |
1 |
2 |
5 |
9 |
7 |
|
2 |
| 7 |
5 |
1 |
9 |
2 |
2 |
1 |
2 |
5 |
9 |
7 |
5 |
| 7 |
5 |
1 |
9 |
5 |
2 |
1 |
2 |
5 |
9 |
7 |
9 |
| 7 |
2 |
1 |
9 |
5 |
2 |
1 |
2 |
5 |
9 |
7 |
7 |
| 7 |
2 |
1 |
9 |
5 |
1 |
1 |
2 |
5 |
9 |
7 |
7 |
| Distance = 2 |
1 |
2 |
5 |
9 |
7 |
7 |
| 7 |
2 |
1 |
9 |
5 |
|
1 |
1 |
2 |
5 |
9 |
7 |
7 |
| 7 |
2 |
7 |
9 |
5 |
1 |
1 |
2 |
5 |
9 |
9 |
7 |
| 1 |
2 |
7 |
9 |
5 |
1 |
1 |
2 |
5 |
7 |
9 |
7 |
| 1 |
2 |
7 |
9 |
5 |
5 |
|
| 1 |
2 |
7 |
9 |
5 |
5 |
| 1 |
2 |
7 |
9 |
5 |
5 |
| 1 |
2 |
7 |
9 |
7 |
5 |
| 1 |
2 |
5 |
9 |
7 |
5 |
| 1 |
2 |
5 |
9 |
7 |
9 |
|
Exemple de programme en Visual Basic
Variantes
Des variantes sont possibles dans la séquence des distances.
- L'une de ces méthodes (appelée 2X) consiste à débuter avec des segments comportant 2 cases, et à multiplier la distance par 2 à chaque étape.
- Une autre méthode consiste à définir la séquence des distances par :
d M =1, d M-1 = d M *3 + 1
Il semble que cette formule ait été obtenue expérimentalement, et que personne n'ait pu expliquer pourquoi elle donnait des résultats optimaux !
Utilisation
Ce tri est moyennement rapide ; plus rapide que le tri par insertion (de part sa définition).
Il est sensible à la répartition initiale des valeurs
Retour à la table des matières des tris
Dernière mise à jour de cette page : 12/8/2007