Staonův svět - Merge Sort na jednosměrném spojovém seznamu

Tak, jak jsem slíbil, dávám sem svoje řešení zadaného úkolu.

Předem upozorňuji, že jestli si to někdo z vás stáhne a odevzdá v této podobě, tak z něho nadělám deset malých do školky! Abych vám to stahování trochu ztížil, tak jsem kód rozdělil na jednotlivé funkce :)

Nejprve trochu teorie. Základním pojmem Merge Sortu je běh (run). Běh je seřazená podposloupnost. Např. pokud mám seřadit vzestupně např. 1 4 7 3 9 2, tak tato posloupnost obsahuje tři běhy: (1 4 7), (3 9) a (2). Hranice běhů jsou taková místa, kde je n-tý prvek větší (pokud řadím vzestupně) než (n + 1)-ní.

Merge Sort pracuje tak, že vždy v jednom kroku algoritmu bere vždy dva běhy za sebou a sloučí je do jednoho nového. V příkladu z předchozího odstavce po prvním cyklu algoritmu vzniknou dva běhy: (1 3 4 7 9), (2) a v dalším cyklu vyrobí jeden běh (1 2 3 4 7 9). Protože v každém kroku snížíme počet běhů na polovinu, časem se dostaneme na jeden běh, tedy na celou posloupnost.

Tak a teď k vlastnímu programu. Myšlenka je následující:

  • zadaný spojový seznam si nejdříve rozdělím na dva tak, že do jednoho dám liché běhy, do druhého sudé.
  • Následně v cyklu slučuji vždy jeden běh z jednoho seznamu a jeden z druhého. Takto vzniklé nové běhy zase postupně sypu nastřídačku do dvou seznamů. Toto provádím tak dlouho, až mi zůstane jen jeden běh.

Je potřeba si uvědomit, že data se nekopírují, pouze se přepojují ukazatele.

Nejdříve definice datových struktur:

  1. type
  2.   PPrvek = ^TPrvek;
  3.   TPrvek = record
  4.     klic: integer;
  5.     dalsi: PPrvek;
  6.   end;
  7.  
  8.   TSeznamy = array[0..POCET_SEZNAMU - 1] of PPrvek;

Na začátku je definice prvků spojového seznamu (dle Bystroně). TSeznamy je dvourozměrné pole pointerů na prvky spojového seznamu. Slouží k uložení vrcholů dvou pomocných seznamů se kterými pracuji a také pro pomocné ukazatele, pomocí kterých cestuji po spojovém seznamu.

Hlavní tělo programu je následující funkce:

  1. procedure MergeSort(var start: PPrvek);
  2. var
  3.   seznamy: TSeznamy;
  4.   vysledky: TSeznamy;
  5.   vstupy, vystupy: TSeznamy;
  6.   index: integer;
  7. begin
  8.   { -- prazdny seznam a jeden prvek nema cenu
  9.        resit }
  10.   if (start <> nil) and (start^.dalsi <> nil) then
  11.   begin
  12.     { -- vyrobim si dva prvky na zacatek seznamu, abych
  13.          nemusel vsude testovat nily }
  14.     seznamyInicializace(seznamy);
  15.     seznamyInicializace(vysledky);
  16.  
  17.     { -- seznam rozdelim na dve casti }
  18.     rozdelSeznam(start, seznamy);
  19.  
  20.     { -- provadim algoritmus tak dlouho, dokud mi nezustane jen
  21.          jeden seznam }
  22.     while (seznamy[0]^.dalsi <> nil) and (seznamy[1]^.dalsi <> nil) do
  23.     begin
  24.       vystupy := vysledky; index := 0;
  25.       seznamyNastav(vstupy, seznamy);
  26.       while(vstupy[0] <> nil) or (vstupy[1] <> nil) do
  27.       begin
  28.         slucBehy(vystupy[index], vstupy);
  29.         index := (index + 1) and 1;
  30.       end;
  31.       { -- nove vytvorene seznamy prepojim na vstupni }
  32.       seznamyPrepoj(seznamy, vysledky);
  33.     end;
  34.  
  35.     { -- vratim vysledne pole }
  36.     if seznamy[0]^.dalsi <> nil then
  37.       start := seznamy[0]^.dalsi
  38.     else
  39.       start := seznamy[1]^.dalsi;
  40.  
  41.     { -- vycistim pamet }
  42.     seznamyZrus(seznamy);
  43.     seznamyZrus(vysledky);
  44.   end;
  45. end;

Proměnná seznamy jsou začátky spojových seznamů, které slouží jako vstupy pro jednotlivé kroky algoritmu. Do těchto seznamů se rozdělí původní vstupní seznam. Proměnná výsledky jsou začátky spojových seznamů, kam se v každém kroku cyklu slučují běhy. A proměnné vstupy a vystupy jsou ukazatele, pomocí kterých se po seznamech pohybuji.

Na řádku 14 a 15 zinicializuji pomocné seznamy. Abych nemusel všude testovat, jestli vkládám do prázdného či neprázdného seznamu, tak si do každého vyrobím na začátek jeden zbytečný prvek.

Na 18. řádku volám funkci, která mi vstupní seznam rozdělí do dvou různých seznamů – jeden s lichými běhy, druhý se sudými (implementace níže).

Na řádkách 22 až 33 je hlavní cyklus algoritmu. Nejdříve si na řádkách 24 a 25 nastavím pomocné posouvací ukazatele na začátky pracovních seznamů (výstupy se nastavují na ony počáteční „dummy“ prvky, výstupy se nastavují na první datové prvky – funkce seznamyNastav). V cyklu 26 a 30 postupně slučuji po jednom běhu z obou seznamů tak dlouho, dokud mám aspoň jeden běh. Změnou proměnné index na řádku 29 postupně přepínám výstupní seznam, do kterého slučuji. Následně na řádku 32 nově vytvořené seznamy přepojím jako vstupní pro další krok cyklu.

  1. procedure rozdelSeznam(start: PPrvek; var seznamy: TSeznamy);
  2. var
  3.   index: integer;
  4.   iter: TSeznamy;
  5. begin
  6.   index := 0; iter := seznamy;
  7.   while start <> nil do
  8.   begin
  9.     { -- zaradim do aktualniho seznamu a posunu se na
  10.          nove zarazeny prvek }
  11.     iter[index]^.dalsi := start;
  12.     iter[index] := iter[index]^.dalsi;
  13.     { -- pokud skoncil run, prepnu na druhy seznam }
  14.     if posunNaDalsi(start) then index := (index + 1) and 1;
  15.   end;
  16.   { -- zakoncim oba nove vytvorene seznamy }
  17.   iter[0]^.dalsi := nil;
  18.   iter[1]^.dalsi := nil;
  19. end;

Funkce rozdelSeznam rozdělí vstupní seznam na dva seznamy, tak že v jednom jsou liché běhy, ve druhém sudé. Princip je jednoduchý, posouvám se seznamem od začátku do konce a přepojuji prvky do výstupního seznamu. Když narazím na hranici běhu, změním výstupní seznam. Funkce posunNaDalsi mi přenastaví ukazatel start na následující prvek (předává se odkazem) a pokud narazí na hranici běhu, vrací true.

  1. function posunNaDalsi(var prvek: PPrvek): boolean;
  2. begin
  3.   if (prvek^.dalsi = nil) or (prvek^.klic > prvek^.dalsi^.klic) then
  4.     posunNaDalsi := true
  5.   else
  6.     posunNaDalsi := false;
  7.   prvek := prvek^.dalsi;
  8. end;

Na řádce 3 testuji hranici běhu, na řádce 7 se posouvám na následníka v seznamu.

  1. procedure slucBehy(var cil: PPrvek; var seznamy: TSeznamy);
  2. var
  3.   konec: boolean;
  4.   index: integer;
  5. begin
  6.   { -- pokud je jeden beh prazdny, neprovadim telo cyklu }
  7.   konec := (seznamy[0] = nil) or (seznamy[1] = nil);
  8.  
  9.   { -- pokud cyklus vubec neprobehne, musim osetrit index, tak
  10.        aby ukazoval na prazdny beh }
  11.   if konec then
  12.   begin
  13.     if seznamy[0] = nil then index := 0 else index := 1;
  14.   end;
  15.  
  16.   { -- dokud mam oba behy, srovnavam je }
  17.   while not konec do
  18.   begin
  19.     if seznamy[0]^.klic <= seznamy[1]^.klic then
  20.       index := 0
  21.     else
  22.       index := 1;
  23.     { -- zaradim mensi prvek do ciloveho seznamu }
  24.     cil^.dalsi := seznamy[index];
  25.     cil := cil^.dalsi;
  26.     konec := posunNaDalsi(seznamy[index]);
  27.   end;
  28.  
  29.   { -- zaradim zbyly nedokonceny beh }
  30.   index := (index + 1) and 1;
  31.   cil^.dalsi := seznamy[index];
  32.   ukonciBeh(seznamy[index], cil);
  33. end;

Poslední podstatná funkce je slucBehy. Na řádce 7 testuji, jestli mám na vstupu oba běhy (ošetření případu, kdy jeden z pracovních seznamů je o jeden běh delší). Pokud nejsou oba, tak na řádkách 11 až 14 si najdu index seznamu, který je prázdný. V cyklu na řádkách 17 až 27 slučuji dva běhy, tak dlouho, dokud mám v obou bězích nějaká data. Princip slučování je jednoduchý. Mám ukazatele na začátek běhů. Najdu, který prvek je menší, tan zařadím do výstupního seznamu a na vstupu se za něj posunu. Na řádkách 30 až 32 přilepím konec běhu, kterému jsem zatím nedošel na konec. Funkce ukonciBeh mi na konec běhu nastaví nil a jako vedlejší efekt nastaví vstupní ukazatel za konec slučovaného běhu a výstupní ukazatel na konec sloučeného běhu.

  1. procedure ukonciBeh(var prvek, cil: PPrvek);
  2. var
  3.   predchozi: PPrvek;
  4. begin
  5.   predchozi := prvek;
  6.   while(not posunNaDalsi(prvek)) do
  7.     predchozi := prvek;
  8.   predchozi^.dalsi := nil;
  9.   cil := predchozi;
  10. end;

Tak a to bylo vše. Ještě tam mám pár pomocných funkcí, které ale nejsou příliš podstatné. Najdete je ve zdrojáku, který si můžete stáhnout zde. BTW, v tom zdrojáku je ještě spousta dalších blbostí navíc, které by tam být neměly, takže ho opravdu předělejte.

Na závěr jen myšlenka o časové složitosti. V každém kroku algoritmu projdu všechny prvky pole (procházím oba seznamy od začátku do konce). Kroků algoritmu dělám maximálně log n, protože běhů je na začátku maximálně n (sestupně seřazená posloupnost) a v každém kroku snížím počet běhů na polovinu. Takže celková složitost je O(n log n).

Ještě možné úpravy, abyste to Bystroňovi neodevzdávali na chlup stejné:

  1. je možné pracovat s více pomocnými seznamy, ne jen se dvěma.
  2. Je možné si určit, že v prvním kroku mám všechny běhy délky 1, ve druhém 2, ve třetím 4, ve čtvrtém 8 atd. Pak si nemusíte hrát s hledáním hranic běhů, protože víte jak jsou dlouhé.
  3. Zkuste, prosím, nepoužívat všichni ten můj malý trik, že mám na začátku seznamu jeden prázdný prvek.
Staon | 4.3.2006 So 01:35 | <<< trvalý odkaz >>> | tisk | 2 komentáře

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
pekna praca
regi 9.3.2006 Čt 19:13

kokso tak nevyzeral ani moj zapoctak :) fakt pekna praca

[2] reaguj
Staon mejl web 10.3.2006 Pá 00:33

[1] regi : no díky, snažil jsem se :)

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Matfyz je sbírka čeho?
Odpověd: malých červených kulatých kostiček naprostých cvoků

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).