Le tri fusion

Admin Messages : 74 Date d'inscription : 02/03/2011

Le tri fusion

Le principe:

Le principe de cet algorithme est très simple. Il consiste à fusionner deux sous-séquences triées en une séquence triée.

Il exploite directement le principe du divide-and-conquer qui repose, grosso-modo, en la division d'un problème en ses sous problèmes et en des recombinaisons bien choisies des sous-solutions optimales.

Le principe de cet algorithme tend à adopter une formulation récursive :

On découpe les données à trier en deux parties plus ou moins égales
On trie les 2 sous-parties ainsi déterminées
On fusionne les deux sous-parties pour retrouver les données de départ

Donc chaque instance de la récursion va faire appel à nouveau au programme, mais avec une séquence de taille inférieure à trier.

La terminaison de la récursion est garantie, car les découpages seront tels qu'on aboutira à des sous-parties d'un seul élément; le tri devient alors trivial.
Une fois les éléments triés indépendamment les uns des autres, on va fusionner (merge) les sous-séquences ensemble jusqu'à obtenir la séquence de départ, triée.

La fusion consiste en des comparaisons successives.
Des 2 sous-séquences à fusionner, un seul élément peut-être origine de la nouvelle séquence. La détermination de cet élément s'effectue suivant l'ordre du tri à adopter.

Une fois que l'ordre est choisi, on peut trouver le chiffre à ajouter à la nouvelle séquence; il est alors retiré de la sous-séquence à laquelle il appartenait.
Cette opération est répétée jusqu'à ce que les 2 sous-séquences soient vides.
Supposons qu'on ait à trier la séquence suivante : [11,4,27,17,32,5,12] par ordre croissant.

Opération de découpage

Cette partie est très simple, elle va consister à découper notre séquence en des sous-séquences de taille presque égales (si le nombre d'éléments de la séquence est impair, on ne saurait pas avoir des tailles rigoureusement égales).

Une fois les découpages effectués, après un certain nombre d'instances, on va avoir des sous-séquences d'un seul élément, comme ceci:

[11] [4] [27] [17] [32] [5] [12]

Bien évidemment, de telles sous-séquences sont triées, vu qu'il n'y a qu'un seul élément.
Le but va maintenant être de fusionner correctement ces listes, chacune triée, entre elles.

Opération de fusion

On va fusionner les listes 2 à 2, ce qui va nous donner 4 sous-listes:

[4,11] [17,27] [5,32] [12]

On continue le processus jusqu'à ce que la liste de départ soit triée. On obtient ainsi:

[4,5,11,12,17,27,32]

qui constitue bien un tri de la séquence de départ.

Voici maintenant une illustration des étapes de l'algorithme avec d'autres données:

[Vous devez être inscrit et connecté pour voir cette image]

L'algorithme peut être décrit 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 car on finit par arriver à des listes composées d'un seul élément et le tri est alors trivial.

L'animation de tri fusion

[Vous devez être inscrit et connecté pour voir ce lien]
Téléchargement de l'animation

Taille:18.23 KB
[Vous devez être inscrit et connecté pour voir ce lien]

Code en Pascal:(mode récursive):

Code:: { ***********PROCEDURE FUSIONNER****************}
procedure fusionner ( var t: vect ; d,m,f : integer);
Var aux, i, j, k : integer;
begin
J:=M;I:=M-1;
WHILE (J<=F) DO
BEGIN
while (T[J] <t[I]) and (i>=1) do
BEGIN
I:=I-1;
END;
Aux:=T[J];
For k:= J DOWNTO I+1 DO
T[k]:=t[K-1];
T[I+1]:=Aux;

J:=J+1;
I:=J-1;
END;
End;
{ ***********PROCEDURE TRI_FUSION****************}
Procedure Tri_Fusion (Var t : veQct; d, f : integer);
Var m:integer;
Begin
If f > d Then
Begin
m := (d + f) Div 2;
afficher(t,d,f);
Tri_Fusion (t, d, m);
Tri_Fusion (t, m + 1, f);
fusionner (t,d,m,f);
afficher(t,d,f);
end;
End;