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 .