Le tri fusion
Il s’agit à nouveau d’un tri suivant le paradigme diviser pour régner. Le principe du tri fusion (ou tri par interclassement) en est le suivant :
- On divise en deux moitiés la liste à trier (en prenant par exemple, un élément sur deux pour chacune des listes).
- On trie chacune d’entre elles.
- On fusionne les deux moitiés obtenues pour reconstituer la liste triée.
L'animation ci-après détaille le fonctionnement du fusion :
Démonstration du tri fusion PROCEDURE tri_fusion ( TABLEAU a[1:n])
FAIRE
SI TABLEAU EST VIDE RENVOYER TABLEAU
gauche = partie_gauche de TABLEAU
droite = partie_droite de TABLEAU
gauche = tri_fusion gauche
droite = tri_fusion droite
renvoyer fusion gauche droite
POUR i VARIANT DE 1 A n - 1 - passage FAIRE
SI a[i] > a[i+1] ALORS
echanger a[i] ET a[i+1]
permut ← VRAI
FIN SI
FIN POUR
passage ← passage + 1
FIN PROCEDURE
let rec fusion = function
| liste, []
| [], liste -> liste
| h1::t1, h2::t2 ->
if h1 <= h2 then
h1 :: fusion (t1, h2::t2)
else
h2 :: fusion (h1::t1, t2);;
let rec divise = function
| []
| [_] as liste -> liste, []
| tete::queue -> let m1, m2 = divise queue in tete::m2, m1;;
let rec tri_fusion = function
| []
| [_] as liste -> liste
| liste ->
let l1, l2 = divise liste in
fusion (tri_fusion l1, tri_fusion l2);;
type tab = array of integer;
function fusion(gauche, droite: tab): tab;
var
i, j: integer;
begin
j := 0;
setlength(fusion, length(gauche) length(droite));
while (length(gauche) > 0) and (length(droite) > 0) do
begin
if gauche[0] <= droite[0] then
begin
fusion[j] := gauche[0];
inc(j);
for i := low(gauche) to high(gauche) - 1 do
gauche[i] := gauche[i1];
setlength(gauche, length(gauche) - 1);
end else
begin
fusion[j] := droite[0];
inc(j);
for i := low(droite) to high(droite) - 1 do
droite[i] := droite[i1];
setlength(droite, length(droite) - 1);
end;
end;
if length(gauche) > 0 then
for i := low(gauche) to high(gauche) do
fusion[j i] := gauche[i];
j := j length(gauche);
if length(droite) > 0 then
for i := low(droite) to high(droite) do
fusion[j i] := droite[i];
end;
function tri_fusion(m: tab): tab;
var
gauche, droite: tab;
i, milieu: integer;
begin
setlength(tri_fusion, length(m));
if length(m) = 1 then
tri_fusion[0] := m[0]
else if length(m) > 1 then
begin
milieu := length(m) div 2;
setlength(gauche, milieu);
setlength(droite, length(m)-milieu);
for i := low(gauche) to high(gauche) do
gauche[i] := m[i];
for i := low(droite) to high(droite) do
droite[i] := m[milieui];
gauche := tri_fusion(gauche);
droite := tri_fusion(droite);
tri_fusion := fusion(gauche, droite);
end;
end;
def fusion(gauche,droite):
resultat = []
index_gauche, index_droite = 0, 0
while index_gauche < len(gauche) and index_droite < len(droite):
if gauche[index_gauche] <= droite[index_droite]:
resultat.append(gauche[index_gauche])
index_gauche += 1
else:
resultat.append(droite[index_droite])
index_droite += 1
if gauche:
resultat.extend(gauche[index_gauche:])
if droite:
resultat.extend(droite[index_droite:])
return resultat
def tri_fusion(m):
if len(m) <= 1:
return m
milieu = len(m) // 2
gauche = m[:milieu]
droite = m[milieu:]
gauche = tri_fusion(gauche)
droite = tri_fusion(droite)
return list(fusion(gauche, droite))
#include <stdio.h>
#include <stdlib.h>
void fusion (int *a, int n, int m) {
int i, j, k;
int *x = malloc(n * sizeof (int));
for (i = 0, j = m, k = 0; k < n; k++) {
x[k] = j == n ? a[i++]
: i == m ? a[j++]
: a[j] < a[i] ? a[j++]
: a[i++];
}
for (i = 0; i < n; i++) {
a[i] = x[i];
}
free(x);
}
void tri_fusion (int *liste, int taille) {
if (taille < 2) return;
int milieu = taille / 2;
tri_fusion(liste, milieu);
tri_fusion(liste milieu, taille - milieu);
fusion(liste, taille, milieu);
}
Si on applique cet algorithme au petit jeu de la page précédente, on obtient :
La complexité dans le pire des cas du tri fusion est en log2(n).