Tri Fusion
Principe
Dans une première phase « Découpe » :
- Découper le tableau en 2 sous-tableaux égaux (à 1 case près)
- Découper chaque sous-tableau en 2 sous-tableaux égaux
- Ainsi de suite, jusqu'à obtenir des sous-tableaux de taille 1
Dans une 2ème phase « Tri/fusion » :
- Fusionner les sous-tableaux 2 à 2 de façon à obtenir des sous-tableaux de taille 2 triés
- Fusionner les sous-tableaux 2 à 2 de façon à obtenir des sous-tableaux de taille 4 triés
- Ainsi de suite, jusqu'à obtenir le tableau entier
Cette méthode est récursive et nécessite l'utilisation d'un tableau secondaire de même taille que le tableau à trier.
Algorithme
TriFusion (Tableau, IMin, IMax)
- Si le tableau ne comporte qu'un élément
- Si le tableau ne comporte que 2 éléments
- Si le tableau comporte plus de 2 éléments
- Milieu = (IMin + IMax) / 2
- TriFusion (Tableau, IMin, Milieu)
- TriFusion (Tableau, Milieu + 1, IMax)
- FusionTableau(Tableau, IMin, Milieu, IMax)
et pour la fusion de 2 sous-tableaux :
FusionTableau(Tableau, IMin, IMed, IMax)
- Créer un tableau T(IMax - IMin + 1)
- I2 = IMed + 1
- I = 0
- Tant que (I1 <= IMed et I2 <= IMax)
- Si Tableau(I1) < Tableau(I2)
- T(I) = Tableau(I1)
- I1 = I1 + 1
- Sinon
- T(I) = Tableau(I2)
- I2 = I2 + 1
- I = I + 1
- Copier le reliquat de Tableau (à partir de I1 ou I2) dans T(à partir de I)
- Recopier le tableau T dans le tableau d'origine, à partir de IMin
Exemple
Tableau à trier : [7,5,1,9,2]
| 1 |
2 |
3 |
4 |
5 |
|
1 |
2 |
3 |
4 |
5 |
|
La phase de découpe en sous-tableaux n'est pas figurée ici |
| Tableau à trier |
Tableau secondaire |
| 7 |
5 |
1 |
9 |
2 |
|
|
|
|
|
| 7 |
5 |
1 |
9 |
2 |
5 |
7 |
1 |
9 |
2 |
Tri/Fusion 2 à 2 |
| 1 |
5 |
7 |
9 |
2 |
5 |
7 |
1 |
9 |
2 |
Tri/Fusion 4 à 4 (détaillé ci-dessous) |
| 1 |
5 |
7 |
9 |
2 |
1 |
2 |
5 |
7 |
9 |
Tri/Fusion 8 à 8 |
| 1 |
2 |
5 |
7 |
9 |
1 |
2 |
5 |
7 |
9 |
Recopie dans le tableau initial |
| Détail du Tri/Fusion de 2 sous-tableaux |
| |
|
|
|
|
|
5 |
7 |
1 |
9 |
|
|
La cellule en gras de chaque sous-tableau indique la position dans le sous-tableau. |
| 1 |
|
|
|
|
5 |
7 |
1 |
9 |
|
| 1 |
5 |
|
|
|
5 |
7 |
1 |
9 |
|
| 1 |
5 |
7 |
|
|
5 |
7 |
1 |
9 |
|
| 1 |
5 |
7 |
9 |
|
5 |
7 |
1 |
9 |
|
Exemple de programme en Visual Basic
Remarques
- L'algorithme étant récursif, son utilisation peut aboutir à une saturation de la pile système avec des tableaux de grande taille.
- Il est préférable, en pratique, de traiter le problème par une boucle. Il est plus simple alors de fusionner directement les éléments 2 à 2, puis 4 à 4, etc ...
Utilisation
Ce tri est assez performant; ses performances sont relativement indépendantes de la répartition initiale des valeurs.
Son gros inconvénient est de nécessiter un doublement du tableau à trier (espace mémoire).
Il est bien adapté au tri de fichiers volumineux (qu'on découpe en sous-fichiers).
Retour à la table des matières des tris
Dernière mise à jour de cette page : 12/8/2007