Řazení slučováním

Řazení slučováním v akci na několika náhodných číslech Řazení slučováním, známé také pod anglickým názvem merge sort, je řadicí algoritmus, jehož průměrná i nejhorší možná časová složitost je (O(N log N)). Algoritmus je velmi dobrým příkladem programátorské metody rozděl a panuj.

Algoritmus vytvořil v roce 1945 matematik John von Neumann.

Algoritmus

Řazení pole s obsahem 7 čísel Algoritmus pracuje následovně: # Rozdělí neseřazenou množinu dat na dvě podmnožiny o přibližně stejné velikosti. +more # Seřadí obě podmnožiny. # Spojí seřazené podmnožiny do jedné seřazené množiny.

Implementace v pseudokódu

function razeni_slucovanim(m) var list levy, pravy if length(m) ≤ 1 return m else stred = length(m) / 2 for each x in m up to stred add x to levy for each x in m after stred add x to pravy levy = razeni_slucovanim(levy) pravy = razeni_slucovanim(pravy) vysledek = sloucit(levy, pravy) return vysledek

Existuje několik variant pro funkci sloucit, toto je nejjednodušší varianta: function sloucit(levy,pravy) var list result while length(levy) > 0 and length(pravy) > 0 if first(levy) ≤ first(pravy) append first(levy) to result levy = rest(levy) else append first(pravy) to result pravy = rest(pravy) while length(levy) > 0 append levy to result levy = rest(levy) while length(pravy) > 0 append pravy to result pravy = rest(pravy) return result

Příklad

Zde je názornější ukázka za pomocí STL algoritmu std::inplace_merge knihovny jazyka C++.

#include #include #include

int main(void) { std::vector data;

for(unsigned i = 0; i (i + m * 2, (unsigned)data.size)); } }

std::cout

Pro porovnání, zde je funkcionální varianta programu zapsaná v jazyce Haskell:

mergeSort [] = [] mergeSort [x] = [x] mergeSort s = merge (mergeSort u) (mergeSort v) where (u,v) = splitAt (n `div` 2) s n = length s

merge s [] = s merge [] t = t merge (x:u) (y:v) = if x

Srovnání s ostatními řadicími algoritmy

Velkou nevýhodou oproti algoritmům stejné rychlostní třídy (např. řazení haldou) je, že řazení slučováním pro svou práci potřebuje navíc pole o velikosti N. +more Existuje sice i modifikace algoritmu, která toto pole nepotřebuje, ale její implementace je velmi složitá a kvůli vysoké režii i pomalá. Kromě toho je řazení slučováním ve většině případů pomalejší než rychlé řazení nebo řazení haldou.

Na druhou stranu je řazení slučováním stabilní řadicí algoritmus, lépe se paralelizuje a má vyšší výkon na sekvenčních médiích s nižší přístupovou dobou. Velkou výhodou proti rychlému řazení je, že čas potřebný pro řazení je téměř nezávislý na počátečním seřazení posloupnosti. +more Vyšší spotřeba paměti není tak velkým problémem jak se může na první pohled zdát, protože při řazení nemusíme manipulovat přímo s položkami řazeného pole, ale pouze s polem indexů, které v paměti většinou zabírá mnohem méně místa. Při použití více indexů můžeme každý index seřadit podle jiného kritéria, což ale není specifické pro řazení slučováním a běžně se používá v databázových indexech. Něco jiného je, že konkrétní řazení může být podle víc kritérií, obvykle zkombinovaných lexikograficky, což ale také není specifické pro tento algoritmus. V mnoha implementacích programovacích jazyků je řazení slučováním implicitním řadicím algoritmem (v Perlu 5. 8, v Javě nebo v GNU C Library).

Pro řazení na sekvenčních médiích se používají jiné algoritmy založené na slučování seřazených (pod)posloupností, které se ale nepovažují za řazení slučováním.

Reference

Externí odkazy

[url=http://www. martinvseticka. +moreeu/index. php. sekce=browse&page=54]Jednoduchá implementace řazení slučováním v jazyku C#[/url] * [url=https://web. archive. org/web/20060719144833/http://24bytes. com/Merge-Sort. html]Řazení slučováním v jazyce C++[/url].

Kategorie:Řadicí algoritmy Kategorie:Stabilní řadící algoritmy