Tri fusion

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

Le tri fusion est un algorithme de tri asymptotiquement optimal (complexité en Θ(nlogn) 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 n'opère pas en place : il a besoin d'une zone temporaire de données de même taille que les données ; par ailleurs, pour des données en mémoire vive, il est en pratique sensiblement plus lent que d'autres algorithmes asymptotiquement optimaux comme le tri par tas.

Sommaire 1 Exemple 1.1 Opération de fusion 1.2 Tri, procedure complète 2 Propriétés 2.1 Implémentations

[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 logn operations de fusion, ici on à 7 éléments, on fait 3 fusions (nécessitant chacune n comparaisons, soit nlogn).

[modifier] Propriétés

1. Le nombre de comparaisons nécessaires est de l'ordre de nlogn.
2. L'espace mémoire requis est de n.

[modifier] Implémentations

Une mise en œuvre simple du tri fusion sur un tableau d'entiers en C :

typedef int tab_entiers[MAX];
 
void fusion(tab_entiers t, tab_entiers tmp, int de1, int vers1, int de2, int vers2, int count, int posInB) 
{
       int i;
       for(i = 0 ; i < count ; i++)
       {
               if(de2 > vers2) 
                       tmp[posInB++] = t[de1++];
               else if(de1 > vers1) 
                       tmp[posInB++] = t[de2++];
               else if(t[de1] <= t[de2]) 
                       tmp[posInB++] = t[de1++];
               else 
                       tmp[posInB++] = t[de2++];
       }
}
 
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 un tableau 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

Les algorithmes de tri

à bulle · par sélection · par insertion · par tas · par base · rapide · fusion · comptage · de Shell