1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| program trifusion;
uses crt;
type vecteur=array [1..100] of real;
var tab,tab1,tab2:vecteur;
c,nf,ns:integer;
{procedure de remplissage du tableau avec des valeurs al‚atoires}
procedure remplitab(var tab:vecteur;n:integer);
var i:integer;
begin
randomize;
for i:=1 to n do
begin
tab[i]:=random(50);
end;
end;
{ procedure d'affichage des elts du tableau}
procedure affichtab(var tab:vecteur;n:integer);
var i:integer;
begin
writeln('Voici les ‚l‚ments du tableau');
for i:=1 to n do
begin
writeln(tab[i]:0:0);
end;
end;
{procedure qui copie les n1 premiers elts du tableau tab ds tab1 et le reste dans tab2}
procedure scinder(tab:vecteur;n:integer;var tab1:vecteur;n1:integer;var tab2:vecteur);
var i,j:integer;
begin
i:=1;
j:=1;
while (i<=n1) do
begin
tab1[i]:=tab[i];
i:=i+1;
end;
while (i<=n) do
begin
tab2[j]:=tab[i];
j:=j+1;
i:=i+1;
end;
end;
{procedure qui copie tab2 a la fin de tab1 de taille initiale n1.la copie
debute … l'indice i2 dans tab2.aprŠs la copie la nvelle taille de tab1 est retourn‚e par la fonction}
function concatener(var tab1:vecteur;n1:integer; tab2:vecteur;n2:integer;i2:integer):integer;
var i:integer;
begin
i:=0;
while (i<n2) do
begin
tab1[n1+1]:=tab2[i2+i];
n1:=n1+1;
i:=i+1;
end;
concatener:=n1;
end;
{procedure qui recopie les elts des tableaux tab1 et tab2 dans tab de fa‡on … ce qu'ils soient tri‚s
les elts de tab1 et tab2 sont suppos‚s tri‚s}
procedure fusionner(var tab:vecteur; tab1:vecteur;n1:integer; tab2:vecteur;n2:integer);
var i1,i2,i:integer;
begin
i1:=1;
i2:=1;
i:=1;
while (i1<=n1) and (i2<=n2) do
begin
if (tab1[i1]<tab[i2]) then
begin
tab[i]:=tab1[i1];
i1:=i1+1;
end
else
begin
tab[i]:=tab2[i2];
i2:=i2+1;
end;
i:=i+1;
end;
i:=concatener(tab,i,tab1,n1-i1,i1);
concatener(tab,i,tab2,n2-i2,i2);
end;
{tri les n elts du tableau tab par la methode de tri par fusion}
procedure trierfusion(var tab:vecteur;n:integer);
begin
if (n>1) then
begin
nf:=n div 2;
ns:=n-nf;
scinder(tab,n,tab1,nf,tab2);
trierfusion(tab1,nf);
trierfusion(tab2,ns);
fusionner(tab,tab1,nf,tab2,ns);
end;
end;
{debut du bloc principal}
begin
clrscr;
gotoxy(20,12);
write('Vous voulez un tableau de combien d''‚l‚ments:');
readln(c);
remplitab(tab,c);
affichtab(tab,c);
trierfusion(tab,c);
affichtab(tab,c);
readln;
end. |
