Verze z 3. 6. 2017, 12:18 editovat 83.240.11.241 (diskuse) Verze 15044058 uživatele 2001:718:2601:26C:4DBC:3838:5A25:F2E0 (diskuse) zrušena značka: možný vandalismus ← Přejít na předchozí porovnání		Verze z 1. 7. 2017, 12:00 editovat zrušit editaci MatSuBot (diskuse \| příspěvky) Roboti 146 386 editací m Robot: odstranění starých interwiki odkazů; kosmetické úpravy Přejít na další porovnání →
Řádek 1: [[~~Image~~Soubor:Merge sort animation2.gif\|frame\|Merge sort v akci na několika náhodných číslech]] '''Merge sort''' je [[řadicí algoritmus]], jehož průměrná i nejhorší možná časová složitost je ([[asymptotická složitost\|''O'']](''N'' log ''N'')). Algoritmus je velmi dobrým příkladem programátorské metody [[rozděl a panuj (algoritmus)\|rozděl a panuj]]. Algoritmus vytvořil v roce [[1945]] [[John von Neumann]]. == Algoritmus == [[~~Image~~Soubor:merge sort algorithm diagram.svg\|thumb\|right\|Ř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. Řádek 11: # Spojí seřazené podmnožiny do jedné seřazené množiny. == Implementace v pseudokódu == '''function''' mergesort(m) Řádek 93: Pro porovnání, zde je funkcionální varianta programu zapsaná v jazyce [[Haskell (programovací jazyk)\|Haskell]]: <source lang="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 <= y then x : merge u (y:v) else y : merge (x:u) v </source> == Srovnání s ostatními řadicími algoritmy == Velkou nevýhodou oproti algoritmům stejné rychlostní třídy (např. [[heapsort]]) je, že Mergesort pro svou práci potřebuje navíc pole o velikosti N. Existuje sice i modifikace Mergesortu, která toto pole nepotřebuje, ale její implementace je velmi složitá a kvůli vysoké režii i pomalá. Kromě toho je Mergesort ve většině případů pomalejší než [[quicksort]] nebo [[heapsort]]. Na druhou stranu je Mergesort [[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 [[quicksort]]u je, že čas potřebný pro řazení je téměř nezávislý na počátečním seřazení posloupnosti. 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 Mergesort 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 Mergesort. V mnoha implementacích programovacích jazyků je Mergesort implicitním řadicím algoritmem (v [[Perl]]u 5.8, v [[Java (programovací jazyk)\|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 Mergesort. == Externí odkazy == * [http://www.martinvseticka.eu/index.php?sekce=browse&page=54 Jednoduchá implementace Merge sortu v C#] * [http://www.24bytes.com/Merge-Sort.html Merge sort v C++] Řádek 120: [[Kategorie:Řadicí algoritmy]] ~~[[no:Sorteringsalgoritme#Flettesortering]]~~

Řazení slučováním: Porovnání verzí