Ocena użytkownikóww: ***** / 11
Nadesłany przez Tomasz Lubiński, 20 listopada 2006 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
Merge Delphi/MergeSortProg.dpr:
// Sortowanie przez scalanie (mergesort)
// Tomasz Lubinski
// (c)2006 www.algorytm.org
program MergeSortProg;
{$APPTYPE CONSOLE}
uses
SysUtils;
const N = 30;
var
i: Integer;
tab: array[0..N-1] of Integer = (30,29,28,27,26,25,1,2,3,4,5,6,7,24,23,22,21,20,19,18,8,9,10,11,17,16,15,13,14,12);
t: array[0..N-1] of Integer; //Tablica pomocnicza
// Scalanie dwoch posortowanych ciagow
// tab[pocz...sr] i tab[sr+1...kon] i
// wynik zapisuje w tab[pocz...kon]
procedure merge(pocz: Integer; sr: Integer; kon: Integer);
var
i,j,q : Integer;
begin
for i:=pocz to kon do t[i]:=tab[i]; // Skopiowanie danych do tablicy pomocniczej
i:=pocz; j:=sr+1; q:=pocz; // Ustawienie wskaźników tablic
while (i<=sr) and (j<=kon) do // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
begin
if (t[i]<t[j]) then
begin
tab[q]:=t[i];
i:=i+1;
end
else
begin
tab[q]:=t[j];
j:=j+1;
end;
q:=q+1;
end;
while (i<=sr) do // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył
begin
tab[q]:=t[i];
q:=q+1;
i:=i+1;
end;
end;
// Procedura sortowania tab[pocz...kon]
procedure mergesort(pocz: Integer; kon: Integer);
var
sr: Integer;
begin
if (pocz<kon) then
begin
sr:=(pocz+kon) div 2;
mergesort(pocz, sr); // Dzielenie lewej części
mergesort(sr+1, kon); // Dzielenie prawej części
merge(pocz, sr, kon); // Łączenie części lewej i prawej
end;
end;
begin
writeln('Zbior przed sortowaniem:');
for i:=0 to N-1 do
write(IntToStr(tab[i]) + ' ');
mergesort(0,N-1);
writeln('');
writeln('Zbior po sortowaniu:');
for i:=0 to N-1 do
write(IntToStr(tab[i]) + ' ');
readln;
end.