Exécution du tri par fusion [Résolu/Fermé]

Signaler
Messages postés
52
Date d'inscription
mardi 3 avril 2007
Statut
Membre
Dernière intervention
3 mars 2009
-
 hachedsamir -
Bonsoir,

voici une procédure qui permet de trier un tableau en utilisant le principe du tri fusion...
en fait, j'ai compris le principe, le problème est que je n'arrive pas à exécuter manuellement la procédure..
La procédure est la suivante:

procedure TriFusion (var a:tab;g, d: integer);
var i, j, k, m: integer;
begin
if g < d then
begin
m := (g + d) div 2;
TriFusion (a,g, m);
TriFusion (a,m + 1, d);
for i := m downto g do b[i] := a[i];
for j := m+1 to d do b[d+m+1-j] := a[j];
i := g; j := d;
for k := g to d do
if b[i] < b[j] then
begin a[k] := b[i]; i := i + 1 end
else
begin a[k] := b[j]; j := j - 1 end;
end;
end;

si quelqu'un pourrait m'aider à comprendre les étapes de l'exécution???????
Cordialement

4 réponses

Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
123
Bonjour,

Le code n'a pas changé, juste commenté et indenté.

procedure TriFusion (var a:tab; g, d: integer);
var i, j, k, m: integer;
begin

   // Si l'indice de début est supérieur à l'indice de fin
   // ( sinon, le tableau est vide ou n'a qu'un élément et est donc trié! )
   if g < d then
   begin
      // Calculer un indice de milieu de tableau
      m := (g + d) div 2;

      // Trier les deux sous tableaux
      TriFusion (a,g, m);
      TriFusion (a,m + 1, d);
      
      // qui est b ?
      // Pour i du milieu au début, stocker les valeurs dans 
      // un tableau intermédiaire...
      for i := m downto g do
         b[i] := a[i];

      // Pour j du milieu à la fin, stocker les valeurs à l'envers dans un 
      // tableau intermédiaire... (Le plus petit à la fin)
      for j := m+1 to d do
         b[d+m+1-j] := a[j];

      // Initialiser les indices de début des deux tableaux
      // (marquant le début du 2ème tableau à la fin car lu à l'envers)
      i := g;
      j := d;

      // Pour k du début à la fin, on fusionne les deux tableaux
      for k := g to d do
         // Si le plus petit de la première moitié est plus petit 
         // que le plus petit de la deuxième moitié...
         if b[i] < b[j] then
         begin
            // On prend celui de la première moitié et augmente l'indice 
            // du début de la première moitié
            a[k] := b[i];
            i := i + 1
         end
         else
         begin
            // On prend celui de la deuxième moitié et diminue l'indice 
            // de "début" de la deuxième moitié
            a[k] := b[j];
            j := j - 1
         end;
   end;
end;


Ainsi sur un tableau a = [ 1 9 2 8 3 7 6 4 5 ]
on a tous les découpages des tableaux

                      [ 1 9 2 8 3 7 6 4 5 ]
[ 1       9       2       8 ] | [ 3       7       6       4   5 ]
[ 1       9 ] | [ 2       8 ] | [ 3       7 ] | [ 6       4   5 ]
[ 1 ] | [ 9 ] | [ 2 ] | [ 8 ] | [ 3 ] | [ 7 ] | [ 6 ] | [ 4   5 ]
                                                      [ 4 ] | [ 5 ]


Ensuite on reconstruit des tableaux en les fusionnant:
l'ordre d'exécution normal est le découpage en deux du tableau initial, puis de la première moitié, du premier quart, du deuxième quart, de la deuxième moitié, du troisième quart, quatrième quart qui est redécoupé en 6 et [4 et 5] puis du [4 et 5]
Chaque tableau de 1 ne passe pas le premier test et la fonction se termine.

Lorsque 1 et 9 remontent ils sont recopiés dans un tableau b (1ère boucle, 1 au début, 2ème boucle, 9 à la fin)
Puis fusionné,
1er tour:
i = 0, j = 1 (pour peu que les indices de tableaux commencent à 0 comme en C, c'est de l'ada ça ?)
a[0] = b[0]
g = g + 1

2eme tour: a [1] = b[1]

puis idem avec 2 et 8 qui forme le tableau [ 2 8 ]

ensuite les tableaux [ 1 9 ] et [ 2 8 ]
recopie des deux tableau dans b -> [ 1 9 8 2 ] (via les deux boucles avec la deuxième moitié à l'envers)
initialisation de i à 0 et de j à 3
puis boucle de 4 tours:
1) 1 < 2 vrai
a[0] = 1
i = i + 1
2) 9 < 2 faux
a[1] = 2
j = j - 1
3) 9 < 8 faux
a[2] = 8
j = j - 1
4) 9 < 9 faux
a[3] = 9
j = j - 1

Il se passe ensuite la même chose pour reformer le tableau [4 5] puis [4 5 6 ] puis [ 3 4 5 6 7 ] puis finalement [ 1 2 3 4 5 6 7 8 9]

Voili voilou, j'espère que cela t'aide à y voire mieux dans les étapes (et que la question n'était pas quelles sont les étapes pour exécuter ce programme ^^")

N'hésite pas si je n'ai pas été clair ou si tu veux que je détaille plus.

Bonne soirée,
M.


PS: C'est pas le but ici mais n'hésite pas à appeler tes variables un peu plus.... enfin, g -> iBegin, d -> iEnd, a -> aValues etc.
Tu pourras aller voir la notation hongroise sur wikipédia si tu es intéressée. Cela consiste à typer le nom de ses variables: i pour integer, a pour array et beaucoup d'autres. Cela parait débile au début mais quand on revient dans un ancien projet ça paye !
2
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 60511 internautes nous ont dit merci ce mois-ci

program ex1;
uses wincrt;
type
mat=array [1..40,1..40] of integer;
tab=array [1..800] of integer;
var
m1,m2,T1:mat;
t:tab;
i,j,c,n,m,n1,n2:integer;
v,v1,v2:tab;
procedure remplir1 (var n,m:integer);
begin
repeat
write('n:=');
readLN(n);
until n in [2..20] ;
repeat
write('m:=');
readLN(m);
until m in [n..20];
end;
procedure remplir2 ( var T1 :mat;n,m:integer);

begin
RANdomize;
for i:=1 to n do
for j:= 1 to m do
t1[i,j]:= random (51);
end;
procedure transfer1 ( T1:mat; var t:tab;n,m:integer; var c:integer );
begin
c:=0;
for i:=1 to n do
for j:= 1 to m do
begin
c:=c+1 ;
t[c]:= T1[i,j] ;
end;
end;
procedure transfer2(var T1:mat; t:tab;n,m:integer; c:integer );
begin
c:=0;
for i:=1 to n do
for j:= 1 to m do
begin
c:=c+1 ;
T1[i,j]:=t[c];
end;
end;
procedure trier ( var t1:mat ; n,m:integer);
var p,aux:integer;
begin
transfer1(T1,t,n,m,c);
for i:=2 to c do
begin
p:=i;
aux:=t[i];
while (p>1) and (aux<t[p-1]) do
begin
t[p]:= t[p-1] ;
p:=p-1;
end;
t[p]:=aux;
end;
transfer2(T1,t,n,m,c);
end;

procedure fusionner (var v:tab; V1,V2:tab; n1,n2:integer);
var c1,c2:integer;
begin
c1:=1;
c2:=1;
c:=0;
repeat
c:=c+1;
if V1[c1]<V2[c2]
then
begin
V[c]:=V1[c1];
c1:=c1+1;
end

else
begin
V[c]:=V2[c2];
c2:=c2+1;
end;
until (c1>n1) or (c2>n2);
begin
if c1>n2
then
for i:=c2 to n2 do
begin
c:=c+1;
V[c]:=V2[i];
end
else
for i:=c1 to n1 do
begin
c:=c+1;
V[c]:=V1[i];
end;
end;
end;

procedure affiche (var T1 :mat;n,m:integer);
begin
for i:= 1 to n do
begin
for j:= 1 to m do
write(T1[i,j]:6);
writeln;
end;
end;

begin
remplir1(n,m);

remplir2(m1,n,m);
writeln('M1 Avant tri : ');
affiche(m1,n,m);
trier(m1,n,m);
writeln('M1 Après tri : ');
affiche(m1,n,m);

readln;

remplir2(m2,n,m);
writeln('M2 Avant tri : ');
affiche(m2,n,m);
trier(m2,n,m);
writeln('M2 Après tri : ');
affiche(m2,n,m);
writeln;

transfer1(m1,v1,n,m,n1);
transfer1(m2,v2,n,m,n2);
fusionner(v,v1,v2,n1,n2);
transfer2(T1,v,2*n,m,n+m);
writeln('Après fusion : ');
affiche(T1,2*n,m);
end.
2
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 60511 internautes nous ont dit merci ce mois-ci

Messages postés
52
Date d'inscription
mardi 3 avril 2007
Statut
Membre
Dernière intervention
3 mars 2009
4
Bonjour,

Merci infiniment Mahmah pour la patience que vous avez prouvé...
Votre explication est bien lisible et l'exemple m'a bien aidé à assimiler.

J'arrive maintenant à comprendre...

Merci une autre fois
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
123
Pas de souci ^^

M.