Nicolas DAILLY
www.dailly.info > Dossiers techniques > Algorithmes de Tri > Tri fusion

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 :

TableauCommentaire : ce qui est fait pour passer à la ligne suivante
6309178254Division du tableau en deux parties
6309178254Division de chaque sous tableau en deux parties
6309178254Division de chaque sous tableau en deux parties
6309178254Division des sous tableau bleu et rouge en deux parties, fusion des tableaux vert-rose
6301978245Fusion des sous tableaux bleu-rose et rouge-rose
3601978245Fusion des sous tableaux bleu-jaune et rouge-jaune
0361927845Fusion des sous tableaux bleu-vert et rouge-vert
0136924578Fusion des deux tableaux
0123456789Le 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(n2). 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(n2), on aurait :

Ce qui est inférieur à n2 dés que n>2. Par conséquent, la complexité du tri fusion n’est pas en O(n2) 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(Nc).
- Si a < bc alors T(N)=O(Nc)
- Si a = bc alors T(N)=O(Nclogb(N))
- Si a > bc alors T(N)=O(Nlogb(a))
- avec logb le logarithme népérien en base b

Ici, on a (2 = 21), 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


© 2000-2017 ~ Nicolas Dailly
Page générée le 25/02/2017 à 14:40:15 ~ Site réalisé avec SPIP