Tri fusion

Principe

Le tri fusion est construit suivant la stratégie "diviser pour régner", en anglais "divide and conquer". Le principe de base de la stratégie "diviser pour régner" est que pour résoudre un gros problème, il est souvent plus facile de le diviser en petits problèmes élémentaires. Une fois chaque petit problème résolu, il n’y a plus qu’à combiner les différentes solutions pour résoudre le problème global. La méthode "diviser pour régner" est tout à fait applicable au problème de tri : plutôt que de trier le tableau complet, il est préférable de trier deux sous tableaux de taille égale, puis de fusionner les résultats.

L’algorithme proposé ici est récursif. En effet, les deux sous tableaux seront eux même triés à l’aide de l’algorithme de tri fusion. Un tableau ne comportant qu’un seul élément sera considéré comme trié : c’est la condition sine qua non sans laquelle l’algorithme n’aurais pas de conditions d’arrêt. Etapes de l’algorithme :

 Division de l’ensemble de valeurs en deux parties
 Tri de chacun des deux ensembles
 Fusion des deux ensembles

Exemple

Grandes étapes de l’évolution du tableau au fil de l’algorithme :

Tableau										Commentaire : ce qui est fait pour passer à la ligne suivante
6	3	0	9	1	7	8	2	5	4	Division du tableau en deux parties
6	3	0	9	1	7	8	2	5	4	Division de chaque sous tableau en deux parties
6	3	0	9	1	7	8	2	5	4	Division de chaque sous tableau en deux parties
6	3	0	9	1	7	8	2	5	4	Division des sous tableau bleu et rouge en deux parties, fusion des tableaux vert-rose
6	3	0	1	9	7	8	2	4	5	Fusion des sous tableaux bleu-rose et rouge-rose
3	6	0	1	9	7	8	2	4	5	Fusion des sous tableaux bleu-jaune et rouge-jaune
0	3	6	1	9	2	7	8	4	5	Fusion des sous tableaux bleu-vert et rouge-vert
0	1	3	6	9	2	4	5	7	8	Fusion des deux tableaux
0	1	2	3	4	5	6	7	8	9	Le tableau est trié, l'algorithme est terminé

Pseudo langage
C / C++		Caml		Java		OCaml
Caml (listes)				OCaml (listes)

Complexité : présentation

Le tri fusion comporte 3 étapes : la division de l’ensemble d’éléments en deux parties, le tri des deux sous-ensembles puis la fusion des deux sous-ensembles triés. Soit un ensemble de n éléments, le coût en nombre d’opérations de la division des deux ensembles est constant dans le cas du tri de tableaux et est de n dans le cas des listes. Le coût du tri des deux sous listes est égal à 2 fois le coût du tri d’une liste de longueur n/2. Enfin, le coût de la fusion des deux sous listes triées est proportionnel au nombre d’éléments à fusionner, c’est à dire en O(n).

Les quelques algorithmes vus jusqu’à maintenant sont en O(n²). D’après les résultats ci dessus, si on note T(n) la complexité du tri fusion pour classer n éléments, on a :

Or, si la complexité du tri fusion était en O(n²), on aurait :

Ce qui est inférieur à n² dés que n>2. Par conséquent, la complexité du tri fusion n’est pas en O(n²) mais en une valeur bien inférieure.

Complexité : calcul

Pour calculer la complexité du tri fusion, nous avons besoin du résultat suivant (qui ne sera pas démontré ici) :

Soit T(N) une suite vérifiant la relation de récurence suivante :
 T(N)=aT(N/b)+O(N^c).
 Si a < b^c alors T(N)=O(N^c)
 Si a = b^c alors T(N)=O(N^clogb(N))
 Si a > b^c alors T(N)=O(N^logb(a))
 avec logb le logarithme népérien en base b

Ici, on a (2 = 2¹), la complexité du tri fusion est donc en O(n*lg(n)) ou lg(n) est le logarithme népérien en base 2.

Remarque : en ce qui concerne le tri de listes, le tri fusion souffre du fait que c’est un algorithme récursif. En effet, pour se dérouler, il doit construire un grand nombre de sous listes, ce qui demande un grand espace mémoire. La complexité en espace mémoire du tri fusion est donc assez handicapante si l’espace mémoire disponible n’est pas assez grand.

---

 Accueil des algorithmes de tri
 Article précédent : le tri Shell
 Article suivant : le tri rapide