Tri fusion

Un article de Wikipédia, l'encyclopédie libre.

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

Le tri fusion est un algorithme de tri asymptotiquement optimal (complexité en $Θ(n log n)$ et consomme $Θ(n)$ en mémoire).

Le tri repose sur le fait que pour fusionner deux listes/tableaux trié(e)s dont la somme des longueurs est n, n-1 comparaisons au maximum sont nécessaires.

Cet algorithme, dans sa version simple, n'opère pas en place : il a besoin d'une zone temporaire de données en O(n) afin d'avoir une vitesse raisonnable. Cependant, des versions plus complexes peuvent être effectués sur place.

Pour aller aussi vite que le tri rapide, il a donc besoin d'utiliser O(n) mémoire supplémentaire, mais il a l'avantage d'être stable (de ne pas mélanger ce qui est déjà trié).

Sommaire

1 Principe général
2 Implémentation avec des tableaux
3 Exemple
- 3.1 Opération de fusion
- 3.2 Tri, procedure complète
4 Propriétés
5 Implémentations
6 Optimisations possibles
7 Liens externes

[modifier] Principe général

L'algorithme peut s'effectuer recursivement :

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

La récursivité s'arrête à un moment car on finit par arriver à des listes de 1 élément et alors le tri est trivial.

On peut aussi faire dans l'autre sens :

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

[modifier] 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 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.

[modifier] Exemple

[modifier] 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), propriété non remarquable sur des listes non 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.

[modifier] Tri, procedure complète

À l'état initial on a les éléments un par un, on les fusionne deux a 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$ operations de fusion, ici on à 7 éléments, on fait 3 fusions (nécessitant chacune n comparaisons, soit $n log n$ ).

[modifier] Propriétés

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

[modifier] Implémentations

Une mise en œuvre simple du tri fusion sur un tableau d'entiers en C. Cette implémentation effectue une fusion vers un tableau temporaire puis recopie les données fusionnées dans le tableau principal.

typedef int tab_entiers[MAX];

// Fusion des listes t(de1..vers1) et t(de2..vers2) dans tmp(posInTmp..posInTmp+count-1)
void fusion(tab_entiers t, tab_entiers tmp, int de1, int vers1, int de2, int vers2, int count, int posInTmp) 
{
       int i;
       for(i = 0 ; i < count ; i++)
       {
               if (de2 > vers2)   // Si fin de la liste 2, on prend dans liste 1
                       tmp[posInTmp++] = t[de1++];
               else if (de1 > vers1)   // Idem si fin de la liste 1
                       tmp[posInTmp++] = t[de2++];
               else if (t[de1] <= t[de2])   // Enfin, sinon, on compare
                       tmp[posInTmp++] = t[de1++];
               else 
                       tmp[posInTmp++] = t[de2++];
       }
}

// Tri de tout le tableau t par fusions successives
void trifusion(tab_entiers t)
{
       tab_entiers tmp;
       int sortLength = 1, de1, de2, de3, i;
       while(sortLength < MAX)
       {
               de1 = 0;
               while(de1 < MAX)
               {
                       de2 = de1 + sortLength;
                       de3 = de2 + sortLength;
                       if(de2>MAX) de2 = MAX;
                       if(de3>MAX) de3 = MAX;
                       fusion(t, tmp, de1, de2-1, de2, de3-1, de3-de1, de1);
                       de1 = de3;
               }
 
               for(i = 0 ; i < MAX ; i++) t[i] = tmp[i];
               sortLength *= 2;
       }
}

Mise en œuvre en Haskell sur des listes d'un type quelconque ordonnable :

tri []  =  []
tri [x] =  [x]
tri xs  =  fusion (tri ys) (tri zs)
  where (ys,zs) =  splitAt (length xs `div` 2) xs
  
        fusion a [] = a
        fusion [] b = b
        fusion a@(x:xs) b@(y:ys) | x <= y     = x : fusion xs b
                                 | otherwise  = y : fusion a ys

[modifier] 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.

[modifier] Liens externes

Tri fusion sur place : un article sur un tri fusion sur place mais pas stable en $O (n log n)$ (fichier au format PostScript)
Tri fusion sur place : algorithme astucieux en C de tri fusion en place et stable, utilisant des rotations d'éléments

v · d · m Les algorithmes de tri
à bulle • par sélection • par insertion • par tas • par base • rapide • fusion • comptage • de Shell

Catégorie : Algorithme de tri