f8p10ps

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.

program mergesort; type vector=arraya1..50i of real ; var v:vector ;n,i:word; procedure schimba(li,ls:word;var a:vector); var man:real; begin if aalii>aalsi then begin man:=aalii; aalii:=aalsi; aalsi:=man; 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 aaii <aaji then begin baki:=aaii; inc(i); end else begin baki:=aaji; inc(j); end; end; if i<=m then for p:=i to m do begin1 inc(k);baki:=aapi; end; if j<=ls then for p:=j to ls do begin inc(k) ;baki:=aapi;

end;

k:=0; for p:=li to ls do begin inc(k); aapi:=baki; 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(vaii); end; divi(1,n,v);
writeln(‘vectorul sortat este:’); for i:=1 to n do writeln(vaii); 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 .