Triedenie zlučovaním - História úprav

Matúš Nečas: /* Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort */

2021-04-19T15:30:06Z

Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort

Matúš Nečas na 17:36, 3. apríl 2021

2021-04-03T17:36:25Z

Filip Tomek: /* Zlučovací algoritmus Merge */

2021-03-30T17:11:52Z

Zlučovací algoritmus Merge

Filip Tomek: /* Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort */

2021-03-29T18:03:38Z

Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort

Matúš Nečas: /* MergeSort */

2021-03-29T18:01:07Z

MergeSort

Matúš Nečas: /* Zlučovací algoritmus Merge */

2021-03-29T17:59:58Z

Zlučovací algoritmus Merge

Matúš Nečas: /* Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort */

2021-03-29T17:59:44Z

Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort

Matúš Nečas: /* Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort */

2021-03-29T17:59:13Z

Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort

Matúš Nečas: /* Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort */

2021-03-29T17:58:53Z

Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort

Matúš Nečas: /* Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort */

2021-03-29T17:58:08Z

Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort

@@ Riadok 139: / Riadok 139: @@
 :::::4.1.5. Skoč na krok 4.1.
 :::4.2. <code>dlzka_podpole *= 2</code>
-:::4.3 Skoč na krok 4.
+:::4.3. Skoč na krok 4.
 </tab>

@@ Riadok 3: / Riadok 3: @@
 {{Skripta programovanie}}
 __TOC__
 ==Zlučovací algoritmus Merge==
 [[Súbor:Funkcia merge.png|500px|náhľad|vpravo|Vizualizácia funkcie ''Merge'': Máme pole prvkov ''p = [1, 3, 5, 2, 4, 6]'', ktoré je už čiastočne utriedené. Použijeme algoritmus ''Merge'', ktorý si vytvorí pomocné polia ''L = [1, 3, 5]'' a ''P = [2, 4, 6]''. Všetky polia indexujeme od ''0'', pričom pre pole ''p'' používame index ''k'', pre ''L'' index ''i'' a pre ''P'' index ''j''. Postupnosť krokov je označená číslicami 1 až 6.
 ]]
@@ Riadok 11: / Riadok 14: @@
 Algoritmus ''Merge'' tvorí kľúčovú časť triediaceho algoritmu ''Merge Sort''.
-===Vlastnosti algoritmu===
+====Vlastnosti algoritmu====
 * vhodný pre dátové štruktúry: pole, lineárny zoznam
 * časová náročnosť: vždy lineárna <math>O(n)</math>
@@ Riadok 17: / Riadok 20: @@
 * využitie: kľúčový podprogram pre triediaci algoritmus ''Merge Sort''
-===Základné časti algoritmu===
+====Základné časti algoritmu====
 # Vytvorenie pomocných polí.
 # Prechádzanie pomocných polí a vyberanie minima z 2 prvkov.
@@ Riadok 23: / Riadok 26: @@
 # Kopírovanie prvkov, ktoré ešte neboli porovnané, z pomocného poľa do výsledného poľa.
-===Slovný opis algoritmu===
+====Slovný opis algoritmu====
 Nech máme vstupné pole, ktoré sa skladá z dvoch už utriedených polovíc. Vytvoríme si dve pomocné polia ''L'' a ''P'' a do každého z nich skopírujeme obsah jednej polovice (''L'' - ľavá polovica, ''P'' - pravá polovica). Potom súčasne prechádzame polia ''L'' a ''P'' od začiatku po koniec, pričom v každej iterácii porovnáme prvok poľa ''L'' s prvkom v poli ''P''. Z tejto dvojice následne vyberieme minimum, (keď triedime od najmenšieho po najväčší) ktoré vložíme na prvú voľnú pozíciu pôvodného poľa (na začiatku je to prvá pozícia poľa). Nakoniec zvýšime index pri vstupnom poli a pri pomocnom poli, z ktorého vyberáme daný prvok. Túto postupnosť krokov opakujeme, pokiaľ neprídeme na koniec jedného z polí ''P'' a ''L''. Ak nastane situácia, že prídeme na koniec jedného z pomocných polí (a v druhom nám ostali ešte nejaké prvky), potom už iba naspäť skopírujeme zbytok druhého pomocného poľa na koniec pôvodného poľa.
-===Pseudokód===
+====Pseudokód====
 Nech funkcia ''Merge'' má nasledovný prototyp: <code>Merge(pole[], lavy, stred, pravy)</code>
 :1. Je <code>lavy >= pravy ? Ak áno, skonči, inak pokračuj krokom 2.</code>
@@ Riadok 55: / Riadok 58: @@
 :::7.4. Skoč na krok 7.
-==Merge Sort==
+===Merge Sort===
 ''Merge Sort'' je triediaci algoritmus, ktorý využíva stratégiu '''"rozdeľuj a panuj"''', čo znamená, že vstupný zoznam najskôr rozdelí na menšie časti, tie zoradí a potom ich zlúči naspäť dokopy. Radí sa medzi najpoužívanejšie a najviac rešpektované triediace algoritmy.
-===Vlastnosti algoritmu Merge Sort===
+====Vlastnosti algoritmu Merge Sort====
 * vhodný pre dátové štruktúry: pole, lineárny zoznam
 * časová náročnosť: vždy linearitmická <math> O(n.log(n)) </math>, vďaka ktorej dokáže efektívne triediť veľmi veľké zoznamy
@@ Riadok 68: / Riadok 71: @@
 Z hľadiska implementácie môžeme vytvoriť dve základné verzie algoritmu, a to ''rekurzívnu'' a ''iteračnú''.
-===Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort===
+====Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort====
@@ Riadok 75: / Riadok 78: @@
 [[Súbor:Merge sort.png|400px|náhľad|vpravo|Vizualizácia rekurzívnej verzie algoritmu Merge Sort: chronologický priebeh algoritmu je znázornený číslicami 1 až 19.]]
-===Základné časti algoritmu===
+====Základné časti algoritmu====
 # Delenie poľa na dve polovice.
 # Triedenie ľavej polovice poľa.
@@ Riadok 81: / Riadok 84: @@
 # Zlúčenie oboch polovíc pomocou funkcie ''Merge''.
-===Slovný opis===
+====Slovný opis====
 Našou úlohou je vzostupne (min -> max) utriediť vstupné pole. Určíme si stred poľa (pri párnom počte prvkov je to ten menší z prostredných indexov). Následne vykonávame sériu rekurzívnych delení pre ľavú a pravú časť poľa (''začiatok ... stred ; stred + 1 ... koniec'') až do momentu, keď nám ostanú len jednoprvkové podpolia (tie sú už utriedené). Následne v každom volaní obe tieto podpolia zlúčime pomocou algoritmu ''Merge'' do väčších podpolí (max: 2, 4, 8, ...), až nakoniec dostaneme jedno výsledné utriedené pole.
-===Pseudokód===
+====Pseudokód====
 Nech má funkcia ''MergeSort'' nasledovný prototyp: <code>MergeSort(pole[], lavy, pravy) </code>
 :1. Je <code>lavy >= pravy</code> ? Ak áno, skonči volanie, inak pokračuj krokom 2.
@@ Riadok 104: / Riadok 107: @@
 [[Súbor:MergeSort IT.png|400px|náhľad|Vizualizácia iteračnej verzie algoritmu Merge Sort: chronologický priebeh algoritmu je znázornený číslicami 1 až 7.|vpravo]]
-===Základné časti algoritmu===
+====Základné časti algoritmu====
 # Určenie maximálnej veľkosti podpoľa na zlučovanie.
 # Prechádzanie jednotlivých podpolí v poli.
 # Zlučovanie jednotlivých podpolí pomocou funkcie ''Merge''.
-===Slovný opis===
+====Slovný opis====
 Vstupné pole, ktoré má ''N'' prvkov, môžeme chápať, ako ''N'' rôznych jednoprvkových (utriedených) podpolí, ktoré máme zlúčiť do jedného výsledného ''N'' - prvkového utriedeného poľa. Keďže by bolo veľmi nepraktické zlučovať ''N'' podpolí naraz, zvolíme nasledovnú stratégiu: Budeme prechádzať dané pole od začiatku po koniec a v prvej iterácii zlúčime každé dva prvky, čím dostaneme <math>\frac{N}{2}</math> dvojprvkových utriedených podpolí. Potom v druhej iterácii zlúčime každé 4 prvky do jedného podpoľa, v treťom cykle každých 8, ..., až do momentu, keď dostaneme jedno výsledné  utriedené pole.
 Aby sme mohli túto stratégiu implementovať, potrebujeme dva cykly: vonkajší, ktorý nastaví maximálnu veľkosť podpoľa, ktoré ideme zlučovať (1,2,4,8 ... ''dlzka - 1'') a vnútorný, ktorý prechádza jednotlivé podpolia. Následne už iba voláme funkciu ''Merge'', ktorá dané podpolia zlučuje.
@@ Riadok 115: / Riadok 118: @@
 Poznámka, ak máme ''pole'', ktoré má nepárny počet prvkov, tak ten posledný prvok nezlúčime hneď v prvej iterácii, ale až v tých ďalších. Takisto, ak ''N'' nie je mocnina čísla 2, tak musíme samozrejme ošetriť situáciu, kedy by sme sa dostali mimo rozsah poľa (Ak máme napríklad ''pole'', čo má 7 prvkov, tak po prvej iterácii budú prvky utiredené podľa vzoru 2 + 2 + 2 + 1, po druhej 4 + 3, a po tretej 7 + 0)
-===Pseudokód===
+====Pseudokód====
 Nech nech má funkcia ''MergeSort'' nasledovný prototyp: <code>MergeSort(pole[], lavy, pravy) </code>
 :1. Je <code>lavy >= pravy</code> ? Ak áno, skonči, inak pokračuj krokom 2.
@@ Riadok 141: / Riadok 144: @@
 </tabs>
-==Implementácia algoritmov Merge a MergeSort v rôznych programovacích jazykoch==
+===Implementácia algoritmov Merge a MergeSort v rôznych programovacích jazykoch===
 <tabs>
 <tab name="Rekurzívna: C " block>

@@ Riadok 10: / Riadok 10: @@
 Algoritmus ''Merge'' tvorí kľúčovú časť triediaceho algoritmu ''Merge Sort''.
 ===Základné časti algoritmu===
@@ Riadok 19: / Riadok 25: @@
 ===Slovný opis algoritmu===
 Nech máme vstupné pole, ktoré sa skladá z dvoch už utriedených polovíc. Vytvoríme si dve pomocné polia ''L'' a ''P'' a do každého z nich skopírujeme obsah jednej polovice (''L'' - ľavá polovica, ''P'' - pravá polovica). Potom súčasne prechádzame polia ''L'' a ''P'' od začiatku po koniec, pričom v každej iterácii porovnáme prvok poľa ''L'' s prvkom v poli ''P''. Z tejto dvojice následne vyberieme minimum, (keď triedime od najmenšieho po najväčší) ktoré vložíme na prvú voľnú pozíciu pôvodného poľa (na začiatku je to prvá pozícia poľa). Nakoniec zvýšime index pri vstupnom poli a pri pomocnom poli, z ktorého vyberáme daný prvok. Túto postupnosť krokov opakujeme, pokiaľ neprídeme na koniec jedného z polí ''P'' a ''L''. Ak nastane situácia, že prídeme na koniec jedného z pomocných polí (a v druhom nám ostali ešte nejaké prvky), potom už iba naspäť skopírujeme zbytok druhého pomocného poľa na koniec pôvodného poľa.
 ===Pseudokód===

@@ Riadok 110: / Riadok 110: @@
 ===Slovný opis===
-Vstupné pole, ktoré má ''N'' prvkov, môžeme chápať, ako ''N'' rôznych jednoprvkových (utriedených) podpolí, ktoré máme zlúčiť do jedného výsledného ''N'' - prvkového utriedeného poľa. Keďže by bolo veľmi nepraktické zlučovať ''N'' podpolí naraz, zvolíme nasledovnú stratégiu: Budeme prechádzať dané pole od začiatku po koniec a v prvej iterácii zlúčime každé dva prvky, čím dostaneme <math>\frac{N}{2}</math> dvojprvkových utriedených podpolí. Potom v druhej iterácii zlúčime každé 4 prvky do jedného podpoľa, v treťom cykle každých 8 ..., až do momentu, keď dostaneme jedno výsledné  utriedené pole.
+Vstupné pole, ktoré má ''N'' prvkov, môžeme chápať, ako ''N'' rôznych jednoprvkových (utriedených) podpolí, ktoré máme zlúčiť do jedného výsledného ''N'' - prvkového utriedeného poľa. Keďže by bolo veľmi nepraktické zlučovať ''N'' podpolí naraz, zvolíme nasledovnú stratégiu: Budeme prechádzať dané pole od začiatku po koniec a v prvej iterácii zlúčime každé dva prvky, čím dostaneme <math>\frac{N}{2}</math> dvojprvkových utriedených podpolí. Potom v druhej iterácii zlúčime každé 4 prvky do jedného podpoľa, v treťom cykle každých 8, ..., až do momentu, keď dostaneme jedno výsledné  utriedené pole.
 Aby sme mohli túto stratégiu implementovať, potrebujeme dva cykly: vonkajší, ktorý nastaví maximálnu veľkosť podpoľa, ktoré ideme zlučovať (1,2,4,8 ... ''dlzka - 1'') a vnútorný, ktorý prechádza jednotlivé podpolia. Následne už iba voláme funkciu ''Merge'', ktorá dané podpolia zlučuje.

@@ Riadok 55: / Riadok 55: @@
 :::7.4. Skoč na krok 7.
-==MergeSort==
+==Merge Sort==
-''MergeSort'' je triediaci algoritmus, ktorý využíva stratégiu '''"rozdeľuj a panuj"''', čo znamená, že vstupný zoznam najskôr rozdelí na menšie časti, tie zoradí a potom ich zlúči naspäť dokopy. Radí sa medzi najpoužívanejšie a najviac rešpektované triediace algoritmy.
+''Merge Sort'' je triediaci algoritmus, ktorý využíva stratégiu '''"rozdeľuj a panuj"''', čo znamená, že vstupný zoznam najskôr rozdelí na menšie časti, tie zoradí a potom ich zlúči naspäť dokopy. Radí sa medzi najpoužívanejšie a najviac rešpektované triediace algoritmy.
 ===Vlastnosti algoritmu Merge Sort===

@@ Riadok 9: / Riadok 9: @@
 Princíp zlučovania tkvie v tom, že máme dva alebo viac utriedených zoznamov, ktoré skombinujeme do jedného utriedeného zoznamu (výsledný zoznam musí obsahovať všetky prvky z pôvodných zoznamov). Zoznam môže byť reprezentovaný ako dátová štruktúra pole alebo aj ako lineárny zoznam. V tomto článku sa zameriame na algoritmus pre dátovú štruktúru pole.
-Algoritmus ''Merge'' tvorí kľúčovú časť triediaceho algoritmu ''MergeSort''.
+Algoritmus ''Merge'' tvorí kľúčovú časť triediaceho algoritmu ''Merge Sort''.
 ===Základné časti algoritmu===

@@ Riadok 73: / Riadok 73: @@
 <tabs>
 <tab name="Rekurzívna verzia" block>
-[[Súbor:Merge sort.png|400px|náhľad|vpravo|Vizualizácia rekurzívnej verzie algoritmu Merge Sort: chronologický priebeh algoritmu je znázornený číslicami 1 - 19]]
+[[Súbor:Merge sort.png|400px|náhľad|vpravo|Vizualizácia rekurzívnej verzie algoritmu Merge Sort: chronologický priebeh algoritmu je znázornený číslicami 1 až 19.]]
 ===Základné časti algoritmu===
@@ Riadok 102: / Riadok 102: @@
 </tab>
 <tab name="Iteračná verzia" block>
-[[Súbor:MergeSort IT.png|400px|náhľad|Vizualizácia iteračnej verzie algoritmu Merge Sort: chronologický priebeh algoritmu je znázornený číslicami 1 - 7|vpravo]]
+[[Súbor:MergeSort IT.png|400px|náhľad|Vizualizácia iteračnej verzie algoritmu Merge Sort: chronologický priebeh algoritmu je znázornený číslicami 1 až 7.|vpravo]]
 ===Základné časti algoritmu===