Mergesort

Princíp triediaceho algoritmu MergeSort (alebo ak chcete po slovensky, triedenia spájaním) je jednoduchý. Použijeme metódu, známu pod názvom rozdeľ a panuj. Tá spočíva v tom, že ak veľký problém nevieme vyriešiť, rozdelíme ho na menšie, ktoré už možno riešiť vieme.

Začnime ale tým, že vyriešime jednoduchší problém. Majme dve utriedené polia čísel. Ako vyrobiť jedno utriedené pole, tvorené všetkými týmito číslami?

Stačí si všimnúť, že najmenšie zo všetkých čísel je na začiatku jedného z polí. Toto číslo presunieme do výsledného poľa... a môžeme celú úvahu zopakovať. Vždy pozrieme na čísla na začiatku každého z polí, vyberieme menšie z nich a to dáme na koniec výsledného poľa.

Čo sa týka konkrétnej implementácie, nechceme prvky z polí vyhadzovať, lebo to zaberá príliš veľa času. Radšej si zoberieme dve premenné, ktoré budú ukazovať na pomyselné začiatky polí. Ak teda „vyhodíme'' prvok zo začiatku poľa, znamená to, že len o 1 zväčšíme premennú ukazujúcu na jeho začiatok. Tiež si treba dať pozor, a kontrolovať, či sme niektoré pole nevyčerpali celé, aby sme nevypadli mimo pamäť.

var A, B, C : array[1..12345] of longint;
    pocetA, pocetB, pocetC : longint;

procedure merge;
{ v poli A mame utriedenych pocetA prvkov
  v poli B mame utriedenych pocetB prvkov
  chceme tieto prvky presunut do pola C }

var poziciaA, poziciaB : longint;
{ potrebujeme si pamatat, kde su najmensie nespracovane prvky }

begin
   poziciaA := 1; poziciaB := 1;
   pocetC := 0;

   { kym este v kazdom z poli mame aspon jeden prvok: }
   while (poziciaA <= pocetA) and (poziciaB <= pocetB) do begin
      { najdeme najmensi nespracovany prvok, presunieme do C }
      if (A[poziciaA] < B[poziciaB]) then begin
         inc(PocetC);
         C[pocetC] := A[poziciaA];
         inc(poziciaA);
      end else begin
         inc(PocetC);
         C[pocetC] := B[poziciaB];
         inc(poziciaB);
      end;
   end;

   { uz sa prvky z jedneho pola minuli, este pridame na koniec 
     zvysok druheho pola }
   while (poziciaA <= pocetA) do begin
      inc(PocetC);  C[pocetC] := A[poziciaA];  inc(poziciaA);
   end;
   while (poziciaB <= pocetB) do begin
      inc(PocetC);  C[pocetC] := B[poziciaB];  inc(poziciaB);
   end;
end;

No a späť k triedeniu. Jedno číslo sa triedi ľahko, ba aj s dvomi si vieme poradiť :) Nuž, ale čo ak ich máme viac? Vtedy rozdelíme pole, ktoré máme utriediť, na dve zhruba rovnako veľké časti. Každú z nich utriedime samostatne. Jediné, čo ešte potrebujeme, je spojiť dve utriedené polia do jedného. A ajhľa, tento problém sme pred chvíľkou vyriešili.

Hm, moment. Čo vlastne znamená "každú z nich utriedime samostatne"? Akoich utriedime? Jednoducho: buď už sú tie časti dosť krátke na to, aby sme ich utriedili rovno, alebo použijeme opäť presne ten istý postup – rozdeliť na dve časti, atď.

No a slová "použijeme presne ten istý postup" napovedajú, že najľahším spôsobom, ako implementovať MergeSort, bude rekurzia (ak nepoznáte rekurziu, zoznámiť sa s ňou môžete v samostatnom článku o rekurzii ). Myšlienka teda bude nasledovná:

procedure MergeSort(pole A);
begin
   rozdel pole A na dve rovnako velke polia B a C;
   MergeSort(B);
   MergeSort(C);
   Merge(B,C) a vysledok uloz do A
end;

Aké rýchle je naše spájanie? Lineárne od počtu prvkov, ktoré spájame.

Poslednou otázkou je časová zložitosť algoritmu. Funkcia merge() zjavne beží v $O(n)$, každé číslo práve raz presunieme do výsledného poľa. Predstavme si teraz, čo robí náš algoritmus. Najskôr rozdelí pole na dve polovice (to je prvá úroveň). Tie rozdelí na dokopy štyri štvrtiny (druhá úroveň) atď. až kým nedosiahne polia veľkosti $1$. Keďže veľkosti častí na úrovniach sa stále delia na polovicu, znamená to, že máme približne $\log n$ úrovní. Otázkou zostáva, koľko práce vykonáme na každej úrovni. Na to si stačí všimnúť, že každý prvok pôvodného poľa je na každej úrovni zastúpený práve raz, teda na každej úrovni je $n$ prvkov. Na každej úrovni použijeme niekoľko volaní lineárneho merge(), ktorým dáme na vstup dokopy $n$ prvkov. To znamená, že spravíme $O(n)$ operácií. Na $\log n$ úrovniach spravíme $O(n)$ operácii, teda výsledný čas je $O(n \log n)$.

Ešte si ukážeme, ako sa dá zaobísť bez použitia priveľa rôznych pomocných polí. Budeme postupne triediť úseky vstupného poľa. Rozdelenie poľa na dve polovice spravíme ľahko – jednoducho necháme všetky prvky na mieste. Samostatne utriedime prvú polovicu a druhú polovicu poľa. Pomocné pole potrebujeme použiť až v okamihu, kedy ideme obe utriedené polovice spojiť. Vyššie ukázaným postupom ich teda spojíme do pomocného poľa, a následne jeho obsah skopírujeme späť do pôvodného poľa.

V Pascale by to celé vyzeralo nasledovne:

var pole,pom : array[0..12345] of longint;
    N,i : longint;

procedure vymen(x,y : longint);
var t : longint;
begin t:=pole[x]; pole[x]:=pole[y]; pole[y]:=t; end;

procedure mergesort(zac,kon : longint);
var stred,a,b,pa,pb,i : longint;
begin
   if (zac = kon) then exit;
   if (zac+1 = kon) then begin
      if (pole[zac] > pole[zac+1]) then vymen(zac,zac+1);
      exit;
   end;
   stred := (zac+kon) div 2;

   mergesort(zac,stred);
   mergesort(stred+1,kon);

   pa:=stred-zac+1;
   pb:=kon-stred;
   a:=0; b:=0;
   while ( (a<pa) and (b<pb) ) do begin
      if (pole[zac+a] < pole[stred+1+b]) then begin
         pom[a+b] := pole[zac+a];
         inc(a);
      end else begin
         pom[a+b] := pole[stred+1+b];
         inc(b);
      end;
   end;
   while (a<pa) do begin pom[a+b] := pole[zac+a]; inc(a); end;
   while (b<pb) do begin pom[a+b] := pole[stred+1+b]; inc(b); end;
   for i:=0 to pa+pb-1 do pole[zac+i] := pom[i];
end;

begin
   readln(N);
   for i:=0 to N-1 do readln(pole[i]);
   mergesort(0,N-1);
   for i:=0 to N-1 do writeln(pole[i]);
end.