Algorithme tri fusion
Je cherche à le retrouver, mais je bloque à plusieurs endroits.
EN gros moi je vois un truc de ce genre:
void trifusion(int *tab, int a, int b)
{
int mid=(a+b)/2;
if(a!=b)
{
trifusion(tab,a,mid);
trifusion(tab,mid+1,b);
}
//on fusionne les deux parties triées
fusion(tab, a, mid, b)
}
Avec la fonction fusion à faire.
Est ce que qqn aurait l'algo complet en C, écrit proprement svp
Merci d'avance @ tous
@+
batmat
Vous hésitez entre Linux et Windows?
Vous voulez dépenser du temps ou de l'argent ?
EN gros moi je vois un truc de ce genre:
void trifusion(int *tab, int a, int b)
{
int mid=(a+b)/2;
if(a!=b)
{
trifusion(tab,a,mid);
trifusion(tab,mid+1,b);
}
//on fusionne les deux parties triées
fusion(tab, a, mid, b)
}
Avec la fonction fusion à faire.
Est ce que qqn aurait l'algo complet en C, écrit proprement svp
Merci d'avance @ tous
@+
batmat
Vous hésitez entre Linux et Windows?
Vous voulez dépenser du temps ou de l'argent ?
8 réponses
-
program fusion01;
uses wincrt;
type
tab=array [1..20]of integer;
var
t:tab;
m,f,d,n:integer;
{---------------------------------------------------}
procedure saisie(var n:integer);
begin
repeat
write('taper la taille du tabeau n : ');
readln (n);
until n in [1..20];
end;
{---------------------------------------------------}
procedure lecture ( var t:tab ;n:integer);
var
i:integer;
begin
for i:=1 to n do
begin
write(' T[',i,']= ');
readln(t[i]);
end;
end;
{---------------------------------------------------}
procedure affiche(var t:tab;d,f:integer);
var
i:integer;
begin
for i:=d to f do
write (t[i],' ');
writeln;
writeln('------------------------------------');
end;
{---------------------------------------------------}
procedure fusion (var t:tab; d,m,f:integer);
var
tr:tab;
i,c1,c2,c3:integer;
begin
tr:=t;
if d<f then
begin c1:=d; c2:=m+1; c3:=d-1;
repeat c3:=c3+1;
if t[c1] <= t[c2] then
begin
tr[c3]:=t[c1]; c1:=c1+1;
end
else
begin
tr[c3]:=t[c2]; c2:=c2+1;
end;
until (c1>m) or (c2>f);
if c1>m then
for i:=c2 to f do
begin c3:=c3+1;
tr[c3]:=t[i];
end
else
if c2>f then
for i:= c1 to m do
begin c3:=c3+1;
tr[c3]:=t[i];
end;
t:=tr;
end;
end;
{---------------------------------------------------}
procedure tri_fusion( var t:tab;d,f:integer);
var
m:integer;
begin
if d<f then
begin
tri_fusion(t,d,m);
tri_fusion(t,m+1,f);
fusion(t,d,m,f);
end;
end;
{---------------------------------------------------}
begin
saisie(n);
lecture(t,n);
affiche(t,1,n);
tri_fusion(t,1,n);
affiche(t,1,n);
end. -
ContributeurY m a pas l air bon ton algo, autant que je me souvienne c est un truc du genre:
Si le tableau a plus de 1 element alors diviser au milieu et trier les 2 parties puis les fusionner
Pour la fusion, ben tu prend le plus petit element entre le 2 premiers elements tu linseres dans ton resultat et tu le vires et tu recommences
Desole, mais pas le temps ni le courage decrire en details, surtout que moi et le C...
ö,ö
\_/ -
Je me souviens avoir mis quelque chose sur CCM, il y a longtemps :
http://www.commentcamarche.com/forum/affich-4573?full>
Je n'ai pas testé, je n'ai pas d'environnement pour le faire, et plus du tout envie de m'y replonger. Sans garantie de transcription correcte (d'après listing). Il faut l'essayer.
Le message comprend un programme principal et 3 méthodes de tri (bulle, quick, fusion). Le "mien" est un tri (en log 2 (n) passes) par fusions de monotonies de longueur 1, 2, 4, ... , la longueur doublant à chaque passe.
La méthode que tu décris se rencontre sur le Net, mais je ne l'ai pas trouvée sous forme de la fonction en C que tu souhaiterais. -
bonjour je cherche un algorithme qui donne un tri croissant à 100 nombres entiers merci!!!
-
tu pe trouver sur internet et tu vas absolument trouver le code en c ou en c++ ou en java,et tu je pense parail a par le code , sauf la declaration de tableau en c a besoin de reserver la memoir avant ,bon courage
-
slt ca va?
svp ki peux m aider pour trouver une solution de tri alphabétique
exercice:
le programme consiste a saisir des mots ( au maximum 10) de 20 caracteres maximum et de les inserer dans un tableau dans l ordre alphabetique . puis d afficher ensuite ce tableau .
le tableau resultat est du type TABLEAU CAR (10,20)
et merci bcp -
slt ca va?
svp ki peux m aider pour trouver une solution de tri alphabétique
exercice:
le programme consiste a saisir des mots ( au maximum 10) de 20 caracteres maximum et de les inserer dans un tableau dans l ordre alphabetique . puis d afficher ensuite ce tableau .
le tableau resultat est du type TABLEAU CAR (10,20)
et merci bcp
repense ;
c'est tres simple que ce soit un tablleau d'entiers ou un tableau de chaines de caractères ça ne change rien en l'algorithme lui meme à part la declaration du tableau
en fait le compilateur admet la comparaison entre les chaines exemple:
'salut' > 'bonjour' :
il faut faire attention au majuscules :
'Bonbon' < 'bonbon' -
program tri_fusion;
uses wincrt;
type
tab=array[1..100]of integer;
var
t:tab;
d,f,n:integer;
{---------------------------------}
procedure taille(varn:integer);
begin
repeat
write('donner la taille du tableau : ');
readln(n);
until n>1;
end;
{---------------------------------}
procedure remplir(var t:tab;n:integer);
var
i:integer;
begin
for i:=1 to n do
begin
write('t[',i,']=');
readln(t[i]);
end;
end;
{---------------------------------}
procedure affiche(t:tab;n:integer);
var
i:integer;
begin
for i:=1 to n do
write(t[i]:5);
writeln;
end;
{---------------------------------}
procedure fusion(var t:tab;d,f:integer);
var
c1,c2,c3,m,i:integer;
v:tab;
begin
m:=(d+f)div 2;
c1:=d;
c2:=m+1;
c3:=d;
v:=t;
repeat
if t[c1] < t[c2] then
begin
v[c3]:=t[c1];
c1:=c1+1;
end
else
begin
v[c3]:=t[c2];
c2:=c2+1;
end;
c3:=c3+1;
until (c1>m)or(c2>f);
if c2>f then
for i:= c1 to m do
begin
v[c3]:=t[i];
c3:=c3+1;
end
else
for i:= c2 to f do
begin
v[c3]:=t[i];
c3:=c3+1;
end;
t:=v;
end;
{---------------------------------}
procedure trier(var t:tab;d,f:integer);
var
m:integer;
begin
m:=(d+f)div 2;
if d<f then
begin
trier(t,d,m);
trier(t,m+1,f);
fusion(t,d,f);
end;
end;
{---------------------------------}
begin
taille(n);
remplir(t,n);
affiche(t,n);
(*fusion(t,1,n);*)
trier(t,1,n);
affiche(t,n);
end.
