Lekce 5 - Merge Sort
V minulé lekci, Heapsort, jsme si ukázali algoritmus Heapsort i se zdrojovými kódy.
Merge sort je algoritmus, založený na tzv. principu rozděl a panuj (latinsky divide et impera, anglicky divide and conquer). To znamená, že pokud nějaký problém neumíme vyřešit v celku, rozložíme si ho na více menších a jednodušších problémů. Ten samý postup aplikujeme i na tyto problémy (opět je rozdělíme na ještě menší, mimochodem velmi se zde nabízí rekurzivní řešení) až se dostaneme na takovou úroveň, kterou jsme schopni bez problému řešit. V problému třídění se často chceme dostat až k poli velikosti 1, které považujeme automaticky za setříděné.
Merge sort operuje s myšlenkou, že dokážeme velmi rychle a v lineárním čase slít (spojit, anglicky merge) dvě již setříděná pole do jednoho tak, aby výsledné pole bylo opět setříděné. Na začátku samozřejmě máme jen jedno pole a to setříděné není. My si ho však můžeme rekurzivně rozdělit na 2 poloviny, každou polovinu opět rozdělit na další poloviny a tak dále. V nejhlubší hladině rekurze se nutně dostaneme do fáze, kdy nám zbydou už jen samá jednoprvková pole. Jednoprvkové pole můžeme považovat za setříděné, říká se o něm, že je setříděné triviálně. Jak se postupně vynořujeme z rekurze, sléváme tato jednoprvková pole na dvouprvková, ta na čtyřprvková a tak pokračujeme, dokud nám nezbydou dvě velká pole, která když slijeme, dostaneme naše původní pole setříděné. Protože sléváme vždy po rozdělení na poloviny, budeme to jistě dělat log n krát (kde základem logaritmu je 2, protože dělíme na 2 poloviny). Samotné slévání zvládneme v čase O(n), výsledná časová složitost algoritmu tedy bude O(n log n). Nejprve si ukážeme, jak se pole slévají.
Slévání
Mějme 2 pole, která jsou již setříděná:
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Všimněte si, že pole nemusí mít stejnou velikost. Když budeme v Merge sortu dělit na polovinu pole o velikosti 7, dostaneme přesně takováto pole. Úskalím Merge sortu je fakt, že budeme potřebovat pomocnou paměť, ta bude zatím prázdná.
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
Začneme tedy slévat. V každém poli budeme potřebovat 2 indexy, které budou zpočátku na prvním indexu. Zde budou zobrazeny tučně.
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
Porovnáme prvky na indexech a ten menší prvek vložíme do pomocného pole na pozici, která je součtem indexů. Oba indexy máme nyní na pozici 0 (první pozice), pozice v pomocném poli tedy bude 0 + 0 = 0. Porovnáme a zjistíme, že 1 < 2, vložíme tedy jedničku na pozici 0 do pomocného pole a index u jedničky zvětšíme o 1.
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
1 |
2 < 4, vložíme tedy dvojku na 0 + 1 = 1 a posuneme se s indexem.
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
1 | 2 |
3 < 4, vložíme 3 na pozici 1 + 1 = 2, posuneme se s indexem.
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
1 | 2 | 3 |
Pokračujeme dále...
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
1 | 2 | 3 | 4 |
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
1 | 2 | 3 | 4 | 5 |
Nyní jsme se dostali do fáze, kdy jsme alespoň s jedním indexů již vyjeli z pole. Nyní se podíváme, zda druhý index není ještě v poli (zde je) a dolijeme zbylé prvky.
2 | 3 | 5 | |
1 | 4 | 7 | 8 |
Pomocná paměť:
1 | 2 | 3 | 4 | 5 | 7 | 8 |
Máme hotovo, výsledné pole je setříděné. V praxi samozřejmě nedostaneme pole už takto připravené na 2 setříděné poloviny, ale pořádně rozházené. Musíme se tedy rekurzí dostat až na jednotková pole a ty poté začít slévat.
Průběh
Průběh označuje následující diagram:
Možná vylepšení
Kamenem úrazu algoritmu je potřebná pomocná paměť. Když se podíváte na diagram výše, vidíte, co všechno si musí funkce držet v paměti. Mohli bychom ovšem třídit naopak, tedy brát původní pole jako již rozdělené na pole jednotková a ta rovnou slévat na pole velikosti 2, ty pak na pole velikosti 4 a podobně. Pomocné paměti bychom se nezbavili, ale při troše práce by stačilo jen jedno pomocné pole, které by bylo stejně velké, jako pole původní. Do něj bychom si uložili výsledek po slití a potom slévali do pole původního a zas naopak. Přelévali bychom tedy data střídavě mezi těmito poli.
Vizualizace
Video ukázka
Vlastnosti algoritmu
Časová složitost | O(n log n) |
---|---|
Stabilita | Ano |
Rychlost | Rychlý |
Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům
Zdrojový kód
-
// sliti dvou setridenych poli do jednoho public static void merge(int[] list, int[] left, int[] right) { int i = 0; int j = 0; // dokud nevyjedeme z jednoho z poli while ((i < left.length) && (j < right.length)) { // dosazeni toho mensiho prvku z obou poli a posunuti indexu if (left[i] < right[j]) { list[i + j] = left[i]; i++; } else { list[i + j] = right[j]; j++; } } // doliti zbytku z nevyprazdneneho pole if (i < left.length) { while (i < left.length) { list[i + j] = left[i]; i++; } } else { while (j < right.length) { list[i + j] = right[j]; j++; } } } // samotne trideni public static void merge_sort(int[] list) { if (list.length <= 1) //podmínka rekurze return ; int center = list.length / 2; //stred pole int[] left = new int[center]; //vytvoreni a naplneni leveho pole for (int i = 0; i < center; i++) left[i] = list[i]; int[] right = new int[list.length - center]; //vytvoreni a naplneni praveho pole for (int i = center; i < list.length; i++) //vytvoreni a naplneni praveho pole right[i - center] = list[i]; merge_sort(left); // rekurzivni zavolani na obe nova pole merge_sort(right); merge(list, left, right); //sliti poli }
-
// sliti dvou setridenych poli do jednoho public static void merge(int[] list, int[] left, int[] right) { int i = 0; int j = 0; // dokud nevyjedeme z jednoho z poli while ((i < left.Length) && (j < right.Length)) { // dosazeni toho mensiho prvku z obou poli a posunuti indexu if (left[i] < right[j]) { list[i + j] = left[i]; i++; } else { list[i + j] = right[j]; j++; } } // doliti zbytku z nevyprazdneneho pole if (i < left.Length) { while (i < left.Length) { list[i + j] = left[i]; i++; } } else { while (j < right.Length) { list[i + j] = right[j]; j++; } } } // samotne trideni public static void merge_sort(int[] list) { if (list.Length <= 1) //podmínka rekurze return ; int center = list.Length / 2; //stred pole int[] left = new int[center]; //vytvoreni a naplneni leveho pole for (int i = 0; i < center; i++) left[i] = list[i]; int[] right = new int[list.Length - center]; //vytvoreni a naplneni praveho pole for (int i = center; i < list.Length; i++) //vytvoreni a naplneni praveho pole right[i - center] = list[i]; merge_sort(left); // rekurzivni zavolani na obe nova pole merge_sort(right); merge(list, left, right); //sliti poli }
-
// sliti dvou setridenych poli do jednoho procedure merge(var list, left, right: array of integer); var i, j: integer; begin i:=0; j:=0; // dokud nevyjedeme z jednoho z poli while ((i < length(left)) and (j < length(right))) do begin // dosazeni toho mensiho prvku z obou poli a posunuti indexu if (left[i] < right[j]) then begin list[i + j]:=left[i]; inc(i); end else begin list[i + j]:=right[j]; inc(j); end; end; // doliti zbytku z nevyprazdneneho pole if (i < length(left)) then begin while (i < length(left)) do begin list[i + j]:=left[i]; inc(i); end; end else begin while (j < length(right)) do begin list[i + j]:=right[j]; inc(j); end; end; end; // samotne trideni procedure merge_sort(var list: array of integer); var center, i: integer; left, right: array of integer; begin if (length(list) <= 1) then exit; // podminka rekurze center:=length(list) div 2; // stred pole setlength(left, center); // vytvoreni a naplneni leveho pole for i:=0 to (center - 1) do left[i]:=list[i]; setlength(right, length(list) - center); // vytvoreni a naplneni praveho pole for i:=center to (length(list) - 1) do right[i - center]:=list[i]; merge_sort(left); // rekurzivni zavolani na obe nova pole merge_sort(right); merge(list, left, right); // sliti poli end;
-
# sliti dvou setridenych poli do jednoho def merge(list, left, right) i = 0 j = 0 # dokud nevyjedeme z jednoho z poli while ((i < left.length) && (j < right.length)) # dosazeni toho mensiho prvku z obou poli a posunuti indexu if (left[i] < right[j]) list[i + j] = left[i] i += 1 else list[i + j] = right[j] j += 1 end end # doliti zbytku z nevyprazdneneho pole if (i < left.length) while (i < left.length) list[i + j] = left[i] i += 1 end else while (j < right.length) list[i + j] = right[j] j += 1 end end end # samotne trideni def merge_sort(list) return if (list.length <= 1) # podminka rekurze center = list.length / 2 # stred pole left = Array.new(center) # vytvoreni a naplneni leveho pole center.times { |i| left[i] = list[i] } right = Array.new(list.length - center) # vytvoreni a naplneni praveho pole center.upto(list.length - 1) { |i| right[i - center] = list[i] } merge_sort(left) # rekurzivni zavolani na obe nova pole merge_sort(right) merge(list, left, right) # sliti poli end
-
{PHP} // sliti dvou setridenych poli do jednoho function merge(array &$list, array $left, array $right) { $i = 0; $j = 0; // dokud nevyjedeme z jednoho z poli while (($i < count($left)) && ($j < count($right))) { // dosazeni toho mensiho prvku z obou poli a posunuti indexu if ($left[$i] < $right[$j]) { $list[$i + $j] = $left[$i]; $i++; } else { $list[$i + $j] = $right[$j]; $j++; } } // doliti zbytku z nevyprazdneneho pole if ($i < count($left)) { while ($i < count($left)) { $list[$i + $j] = $left[$i]; $i++; } } else { while ($j < count($right)) { $list[$i + $j] = $right[$j]; $j++; } } } // samotne trideni function merge_sort(array &$list) { if (count($list) <= 1) // podmínka rekurze return ; $center = count($list) / 2; // stred pole $left = []; // vytvoreni a naplneni leveho pole for ($i = 0; $i < $center; $i++) $left[$i] = $list[$i]; $right = []; // vytvoreni a naplneni praveho pole for ($i = $center; $i < count($list); $i++) // vytvoreni a naplneni praveho pole $right[$i - $center] = $list[$i]; merge_sort($left); // rekurzivni zavolani na obe nova pole merge_sort($right); merge($list, $left, $right); // sliti poli } $list = [17, 1, 3, 28, 8, 7, 4, 2]; merge_sort($list); print_r($list); {/PHP}
V další lekci, Quick sort, si ukážeme algoritmus Quick sort i se zdrojovými kódy.