Tri fusion

Tri fusion appliqué à un tableau de 7 éléments.

Le tri fusion est un algorithme de tri stable par comparaison. Sa complexité temporelle pour une entrée de taille n est de l'ordre de n log n, ce qui est asymptotiquement optimal. Le tri fusion se décrit naturellement sur des listes, mais fonctionne aussi sur des tableaux.

Ce tri est basé sur la technique algorithmique diviser pour régner. L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une seule. L'efficacité de l'algorithme vient du fait que deux listes triées peuvent être fusionnées en temps linéaire.

La version la plus simple du tri fusion sur les tableaux a une efficacité comparable au tri rapide, mais elle n'opère pas en place : une zone temporaire de données supplémentaire de taille égale à celle de l'entrée est nécessaire. Des versions plus complexes peuvent être effectuées sur place mais sont moins rapides.

Algorithme

L'algorithme peut être décrit récursivement :

1. On découpe en deux parties à peu près égales les données à trier
2. On trie les données de chaque partie
3. On fusionne les deux parties

La récursivité s'arrête car on finit par arriver à des listes composées d'un seul élément et le tri est alors trivial.

En pseudo-code, l'algorithme pourrait s'écrire ainsi :

  fonction scinder(liste0) : 
     si longueur(liste0) <= 1, renvoyer le couple (liste0, liste_vide)
     sinon, 
        soient e1 et e2 les deux premiers éléments de liste0, et reste le reste de liste0
        soit (liste1, liste2) = scinder(reste) 
        renvoyer le couple de listes (liste de tête : e1 et de queue : liste1, liste de tête : e2 et de queue : liste2)

  fonction fusionner(liste1, liste2) :
     si la liste1 est vide, renvoyer liste 2 
     sinon si la liste2 est vide, renvoyer liste 1
     sinon 
        si tête(liste 1) <= tête(liste2), renvoyer la liste de tête : tête(liste1) et de queue : fusionner(queue(liste1),liste2)
        sinon, renvoyer la liste de tête : tête(liste2) et de queue : fusionner(liste1,queue(liste2)) 
        
  fonction triFusion(liste0) :
     si longueur(liste0) <= 1, renvoyer liste0
     sinon,
        soit (liste1, liste2) = scinder(liste0)
        renvoyer fusionner(triFusion(liste1), triFusion(liste2))

On peut aussi utiliser un algorithme itératif :

1. On trie les éléments deux à deux
2. On fusionne les listes obtenues
3. On recommence l'opération précédente jusqu'à ce qu'on ait une seule liste triée

Implémentation avec des tableaux

Avec des tableaux, on peut faire le tri sur place ou non. On a alors schématiquement trois possibilités de gestion de la mémoire :

• On fait le traitement sur place. On commence par trier les paires ou les triades d'éléments sur place puis on fusionne sur place les listes adjacentes entre elles. La procédure de fusion s'applique alors à un sous-tableau contenant deux listes l'une après l'autre. Pour fusionner en place, l'implémentation simple, qui consiste à décaler la première liste quand on insère un ou plusieurs éléments de la deuxième, est lente (un peu comme un tri par insertion). D'autres algorithmes plus rapides existent, mais ils sont compliqués et souvent ne sont pas stables (ne conservent pas l'ordre précédent). Voir le lien externe plus bas.

• On fait le traitement à moitié sur place. On commence par trier les paires ou les triades d'éléments sur place puis on fusionne. Lors de la fusion, on effectue une copie de la première liste en mémoire temporaire (on peut faire une copie des deux listes, mais ce n'est pas nécessaire). Ainsi on a plus besoin de décaler les données, on copie simplement un élément de la première liste (depuis la mémoire temporaire) ou de la deuxième liste (qui est gardée sur place). Cette implémentation est plus rapide (plus rapide qu'un tri par tas mais plus lente qu'un tri rapide).

• On utilise une zone temporaire de même taille que le tableau à trier. On peut alors faire les fusions d'un des tableaux à l'autre. Trier un seul élément revient alors à le recopier d'un tableau à l'autre, trier deux éléments revient à les copier de manière croisée ou non etc. Cette fois, lors de la fusion, quand on copie le premier élément de la première liste ou de la deuxième, on n'a pas besoin de décaler les données, ni de recopier la première liste. Cette implémentation a une complexité comparable au tri rapide, sans avoir l'inconvénient du pire des cas quadratique. Ce tri fusion fait plus de copies qu'un tri rapide mais fait moins de comparaisons.

Exemple

Opération de fusion

Fusionner [1;2;5] et [3;4] : on sait que le premier élément de la liste fusionnée sera le premier élément d'une des deux listes d'entrée (soit 1, soit 3) car ce sont des listes triées.

On compare donc 1 et 3 → 1 est plus petit.

[2;5] - [3;4] → [1]

On compare 2 et 3 → 2 est plus petit.

[5] - [3;4] → [1;2]

On compare 5 et 3 → 3 est plus petit.

[5] - [4] → [1;2;3]

On compare 5 et 4 → 4 est plus petit.

[5] → [1;2;3;4]

[1;2;3;4;5]

Bien sûr ce n'est qu'une étape du tri.

Tri, procédure complète

À l'état initial on a les éléments un par un, on les fusionne deux à deux:

([6] [1]) ([2] [5]) ([4] [7]) [3]

On obtient:

([1;6] [2;5]) ([4;7] [3]) que l'on fusionne deux à deux à nouveau et ainsi de suite:

([1;2;5;6] [3;4;7])

[1;2;3;4;5;6;7]

Remarque : On fait log n opérations de fusion, ici on a 7 éléments, on fait 3 fusions (nécessitant chacune n comparaisons, soit nlog n).

Propriétés

1. Le nombre de comparaisons nécessaires est de l'ordre de nlog n.
2. L'espace mémoire requis est en O(n) à moins de faire des rotations d'éléments.

Optimisations possibles

• Au niveau de l'utilisation de la mémoire :
  • On peut limiter la mémoire utilisée à n/2 éléments en recopiant seulement la première des deux listes à fusionner en mémoire temporaire.
  • On peut limiter la mémoire utilisée à O(1) en ne recopiant pas les éléments. On peut fusionner en faisant une rotation des éléments allant du milieu de la première liste au milieu de la deuxième.

• Au niveau de la vitesse d'exécution :
  • On peut avoir la rapidité d'exécution de la copie d'un tableau à un autre, tout en utilisant un tableau temporaire de taille n/2 seulement. Soit A la première et B la deuxième moitié du tableau à trier, et C le tableau temporaire de taille n/2. On trie en copiant les éléments entre A et C, puis entre A et B. Enfin, on fusionne les listes obtenues en B et C dans le tableau entier AB.

Voir aussi

Sur les autres projets Wikimedia :

• « Tri fusion », sur Wikibooks (livres pédagogiques)

Liens externes

• (en) Java utilise une variante du tri fusion pour ses tris de l'objet Collections
• Tri fusion sur place : un article sur un tri fusion sur place mais pas stable en O(nlogn) (fichier au format PostScript)
• Tri fusion sur place : algorithme astucieux en Java de tri fusion en place et stable, utilisant des rotations d'éléments