Sortare prin interclasare(mergesort)
Tabloul unidimensional V se completeaza cu n numere reale. Sa se ordoneze crescator folosind sortare prin interclasare.
Sortarea prin interclasare se bazeaza pe urmatoarea logica :
vectorul V se imparte ,prin injumatatiri succesive ,in vectori din ce in ce mai mici ;cand se ating vectorii de maxim doua elemente ,fiecare dintre acestia se ordoneaza printr-o simpla comparare a elementelor ;cate doi astfel de mini- vectori ordonati se interclaseaza succesiv pana se ajunge iar la vectorul V. 39734mmu66nko3q
program mergesort;
type vector=array[1..50] of real ;
var v:vector ;n,i:word;
procedure schimba(li,ls:word;var a:vector);
var man:real;
begin
if a[li]>a[ls] then begin
man:=a[li];
a[li]:=a[ls];
a[ls]:=man; mk734m9366nkko
end;
end;
procedure interclas(li,m,ls:word;var a:vector);
var b:vector:i,k,p,j:word;
begin
i:=li; j:=m+1; k:=0;
while (i<=m)and(j<=ls) do
begin
inc(k);
if a[i] <a[j] then begin
b[k]:=a[i];
inc(i);
end
else begin
b[k]:=a[j];
inc(j);
end;
end;
if i<=m then for p:=i to m do begin1
inc(k);b[k]:=a[p];
end;
if j<=ls then for p:=j to ls do begin
inc(k) ;b[k]:=a[p];
end;
k:=0;
for p:=li to ls do begin
inc(k);
a[p]:=b[k];
end;
end;
procedure divi(li,ls:word; var a:vector);
var m:word;
begin
if (ls-li)<=1 then schimba(li,ls,a);
else begin
m:=(li+ls)div 2;
divi(li,m,a);
divi(m+1,ls,a);
interclas(li,m,ls,a);
end;
end;
begin
write(‘cate elemente are vectorul?=’);readln(n);
for i:=1 to n do
begin
write(‘tastati elementul’,i,’=’);
readln(v[i]);
end;
divi(1,n,v);
writeln(‘vectorul sortat este:’);
for i:=1 to n do writeln(v[i]);
end.
OBSERVATII
4mecanismul general de tip Divide et Impera se gaseste implementat in procedura “divi” ;
4o astfel de abordare a problemei sortarii unii vector conduce la economie de timp de calcul ,deoarece operatia de interclasare a doi vectori deja ordonati este foarte rapida ,iar ordonarea independenta celor doua jumatati(mini- vectori) consuma in total aproximativ a doua parte din timpul care ar fi necesar ordonarii vectorului luat ca intreg .
