Tri fusion
Le tri fusion est un algorithme de tri asymptotiquement optimal (complexité en et consomme 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é).
Principe général
L'algorithme peut s'effectuer récursivement :
- 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
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.
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), 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.
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 opérations de fusion, ici on a 7 éléments, on fait 3 fusions (nécessitant chacune n comparaisons, soit ).
Propriétés
- Le nombre de comparaisons nécessaires est de l'ordre de .
- L'espace mémoire requis est en O(n) à moins de faire des rotations d'éléments.
Mises en œuvre
C
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;
}
}
Haskell
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
Java
Mise en œuvre Java (ou C#) :
public static void triFusion (int [] tab, int début, int fin){
int milieu;
if(début<fin){
milieu = (début+fin)/2;
triFusion(tab, début, milieu);
triFusion(tab, milieu+1, fin);
fusionner (tab, début, milieu, fin);
}
}
public static void fusionner (int tab[], int début, int milieu, int fin){
int [] t1 = new int[milieu-début];
int [] t2 = new int[fin-(milieu+1)];
for(int i = début; i <= milieu ; i++){
t1[i] = tab[i];
}
for(int i = milieu+1; i <= fin; i++){
t2[i] = tab[i];
}
int i1 = début; //indice t1
int i2 = milieu+1; // indice t2
int i = début; //indice tab
while(i1<= milieu && i2 <= fin){
//quelle est la plus petite tête de liste?
if(t1[i1] <= t2[i2]){
tab[i] = t1[i1];
i1++;
}else{
tab[i] = t2[i2];
i2++;
}
i++;
}
if (i<=fin){
while(i1<=milieu){ // le reste de t1
tab[i]=t1[i1];
i1++;
i++;
}
while(i2<=fin){ // le reste de t2
tab[i]=t2[i2];
i2++;
i++;
}
}
}
Ocaml
Tri fusion de vecteurs en Caml :
let rec triFusion v =
let rec l = Array.length v in
let rec div =
let g = Array.sub v 0 (l/2)
and d = Array.sub v (l/2) ((l+1)/2) in
(g,d)
and fus g d t lg ld =
if lg = 0 && ld = 0 then t
else if lg = 0 then Array.append t d
else if ld = 0 then Array.append t g
else if g.(0) <= d.(0) then fus (Array.sub g 1 (lg-1)) d (Array.concat [t;[|g.(0)|]]) (lg -1) ld
else fus g (Array.sub d 1 (ld-1)) (Array.concat [t;[|d.(0)|]]) lg (ld -1)
in
if l <= 1 then v
else if l=2 then [|min v.(0) v.(1);max v.(0) v.(1)|]
else fus (triFusion (fst div)) (triFusion (snd div)) [||] (l/2) ((l+1)/2)
Tri fusion en utilisant les listes chainées avec Ocaml :
Le code est séparé en trois fonctions pour plus de clarté. couperListe : prend une liste non triée en paramètre et sépare son contenu en deux listes toujours non triées, dont les longueurs diffèrent d'au plus un. fusionnerListes : prend deux listes triées en paramètre et renvoie une liste triée content l'ensemble des éléments des deux listes. triFusion : fonction qui se charge d'appeler les deux autres, elle découpe une liste non triée avec couperListe puis trie récursivement les deux listes résultantes avec triFusion, qu'elle fusionne ensuite avec fusionnerListes.
let rec couperListe = function
([] | [_]) as singleton -> singleton, [] (* Il est strictement identique de renvoyer ([], singleton) *)
| element1 :: element2 :: queue ->
let liste1, liste2 = couperListe queue in
(element2 :: liste1, element1 :: liste2) (* On rajoute chaque élément dans une des deux listes *)
;;
let rec fusionnerListes (liste1, liste2) = match (liste1, liste2) with
|([], liste) | (liste, []) -> liste (* Si une des deux listes à fusionner est vide, on renvoie tout simplement la liste non-vide *)
| (tete1 :: queue1, tete2 :: queue2) ->
if tete1 < tete2 then tete1 :: fusionnerListes (queue1, liste2) (* On met la plus petite tête des deux listes en tête de la liste final et on fusionne le reste de la même manière *)
else tete2 :: fusionnerListes (queue2, liste1)
;;
let rec triFusion= function
([_] | []) as singleton -> singleton (* Si la liste ne contient qu'un élément, elle est forcément déjà triée *)
| liste -> let liste1, liste2 = couperListe liste in
fusionnerListes (triFusion liste1, triFusion liste2) (* On trie les deux listes avec triFusion et on les assemble *)
;;
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
Article connexe
Liens externes
- Tri fusion sur place : un article sur un tri fusion sur place mais pas stable en (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