Tri fusion

Publié : 10/05/2014 · Modifié : 13/12/2015


Table des matières

Introduction

Le tri fusion (merge sort en anglais) est un algorithme de tri par comparaison efficace qui a pour complexité $O(N \log _2 N)$, il se base sur le principe du diviser pour régner. Cet algorithme est stable mais ne s’exécute pas en place.

Principe de l’algorithme

L'algorithme se compose de deux parties distinctes :

L'intérêt de diviser pour ensuite fusionner est que créer un tableau trié à partir de deux sous tableaux peut s'effectuer en temps linéaire. C'est ce point en particulier qui fait la rapidité du tri fusion.

Exemple

Prenons comme exemple la suite de nombre : 5, 1, 3, 8, 9, 6 que l’on veut trier avec le tri fusion dans l’ordre croissant :

1ère étape : diviser

5, 1, 3 | 8, 9, 6 -> on divise le tableau en deux.

5, | 1, 3 | 8 | 9, 6 -> on divise en deux les sous tableaux.

5 | 1 | 3 | 8 | 9 | 6 -> chaque sous tableau est de nouveau divisé pour n'avoir plus qu'un seul élément.

2ème étape : fusionner

1, 5 | 3, 8 | 6, 9 -> on prend deux sous tableaux adjacents que l'on fusionne en les ordonnant.

1, 3, 5, 8 | 6, 9 -> on continue la fusion des sous tableaux.

1, 3, 5, 6, 8, 9 -> le tableau ne contient plus de sous tableaux, il est donc trié.

1, 3, 5, 6, 8, 9

Pour résumer les deux étapes du tri :

Exemple de tri fusion
Exemple de tri fusion

Les éléments en bleu correspondent à l'état du tableau après la première étape, et les éléments en vert après la deuxième étape.

Pseudo-code

Voici le pseudo-code du tri fusion :

triFusion (début, fin) :

   Si le tableau a un seul élément
      Arrêter
   Sinon
      triFusion(début, milieu)
      triFusion(milieu + 1, fin)

      fusionner(début, milieu, fin)

fusionner (début, milieu, fin) :

   A -> éléments du tableau de début à milieu
   B -> éléments du tableau de milieu + 1 à fin

   Pour i allant de début à fin
      Si A[indexA] <= B[indexB]
         Tableau[i] = A[indexA]
         Incrémenter indexA 
      Sinon
         Tableau[i] = B[indexB]
         Incrémenter indexB

Ce pseudo-code est relativement simple :

Complexité

Pour démontrer la complexité du tri fusion, visualisons la découpe du tableau réalisée dans la fonction triFusion lors des appels récursifs :

Calcul de la complexité
Calcul de la complexité

Les deux appels récursifs sont représentés par une séparation du tableau actuel en deux, et ce qu'il faut comprendre c'est que tous les sous tableaux d'une même profondeur formeront toujours un unique tableau contenant $N$ éléments ($N$ étant la taille du tableau de départ), puisqu'on divise par deux la taille, mais on multiplie par deux le nombre de nœuds. C'est très important car on appelle notre fonction fusionner à chaque nœud, or cette fonction s'exécute en temps linéaire de $O(N)$ avec $N$ la taille du sous tableau. On peut donc dire grâce aux deux dernières informations, qu'à chaque profondeur on aura appelé notre fonction fusionner sur $N$ éléments (quelle que soit la profondeur). De plus, on sait que cet arbre possède $\log _2 N$ profondeurs (pour en savoir plus sur le logarithme : lien de la page Wikipédia), ce qui nous donne finalement une complexité en $O(N \log _2 N)$.

Implémentation

Une implémentation en C du tri fusion :

tri_fusion.c

L'entrée du programme :

6
5 1 3 8 9 6

Et en sortie, notre tableau trié :

1 3 5 6 8 9

Améliorations et variantes

Liste chaînée

Les listes chaînées sont effectivement un bon moyen d'implémenter le tri fusion à cause de cette flexibilité que ce tri impose. En effet, on doit pouvoir séparer des éléments pour les fusionner dans un ordre différent après, et ces opérations ne sont pas pratiques ni optimales avec des tableaux, mais sont adaptées à des listes chaînées.

La complexité en temps reste la même, mais la complexité en mémoire est améliorée.

Conclusion

Le tri fusion est donc un algorithme de tri efficace, qui a pour complexité $O(N \log _2 N)$. Cependant, cet algorithme est finalement peu utilisé en pratique à cause du tri rapide qui est meilleur dans de nombreux domaines (gestion du cache, nombre de comparaisons, possibilité d'améliorations, etc.).