Nu aveti permisiuni pentru a descarca fisierul grader_test10.in
Cod sursa(job #469877)
Utilizator | E1 La5c01 05_Yohn | Data | 9 iulie 2010 14:28:09 |
---|---|---|---|
Problema | Sortare prin comparare | Scor | 0 |
Compilator | fpc | Status | done |
Runda | Arhiva educationala | Marime | 1.48 kb |
{Algoritmul Merge Sort}
{O(NlogN)}
{sa vedem, sa vedem .. ce-o sa iasa :D}
program merge_sort;
var {buf:array[1..102400]of byte}
w,v:array[1..100]of integer;
i,n:longint;
procedure sort(a,b:longint);
var i,j,imax,jmax,k:longint;
begin
if a<b then begin
sort(a,(a+b)div 2); {impartim pe jumatate in 2 liste}
sort(((a+b)div 2)+1,b); {sortam fiecare lista}
i:=a; {luam fiecare cap de lista}
imax:=(a+b)div 2; {impreauna cu sfarsitul ei}
j:=((a+b)div 2)+1;
jmax:=b;
k:=1; {noul vector}
while (i<=imax)and(j<=jmax) do {suprapunem listele}
if v[i]<v[j] then begin
w[k]:=v[i];
inc(i);
inc(k);
end
else begin
w[k]:=v[j];
inc(j);
inc(k);
end;
dec(k);
if i<=imax then begin
for j:=i to imax do w[k+j-i+1]:=v[j];
k:=k+imax-i+1;
end
else if j<=jmax then begin
for i:=j to jmax do w[k+i-j+1]:=v[i];
k:=k+jmax-j+1;
end;
for i:=1 to k do v[a+i-1]:=w[i];
end;
end;
begin
assign(input,'algsort.in');
reset(input);
{SetTextBuf(input,buf); {parsam un pic citirea :P}
read(n);
for i:=1 to n do read(v[i]);
sort(1,n);
assign(output,'algsort.out');
rewrite(output);
for i:=1 to n do write(w[i],' ');
close(output);
end.