Merge sort
Z Wikipedie, otevřené encyklopedie
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.
Obsah |
[editovat] Algoritmus
Algoritmus pracuje následovně:
1) Rozdělí neseřazenou množinu dat na dvě podmnožiny o přibližně stejné velikosti
2) Seřadí obě podmnožiny
3) Spojí seřazené podmnožiny do jedné seřazené množiny
Algoritmus vytvořil v roce 1945 John von Neumann.
[editovat] Implementace v pseudokódu
function mergesort(m)
var list left, right
if length(m) ≤ 1
return m
else
middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = mergesort(left)
right = mergesort(right)
result = merge(left, right)
return result
Existuje několik variant pro funkci merge(), toto je nejjednodušší varianta:
function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
if length(left) > 0
append left to result
if length(right) > 0
append right to result
return result
[editovat] Příklad
Zde je názornější ukázka za pomocí STL algoritmu std::inplace_merge.
#include <iostream> #include <vector> #include <algorithm> int main(void) { std::vector<unsigned> data; for(unsigned i = 0; i < 10; i++) data.push_back(i); std::random_shuffle(data.begin(), data.end()); std::cout << "Initial: "; for(unsigned i = 0; i < 9; i++) std::cout << data.at(i) << " "; std::cout << data.at(9) << "." << std::endl; for(unsigned m = 1; m <= data.size(); m *= 2) { for(unsigned i = 0; i < data.size() - m; i += m * 2) { std::inplace_merge( data.begin() + i, data.begin() + i + m, data.begin() + std::min<unsigned>(i + m * 2, (unsigned)data.size())); } } std::cout << "Sorted: "; for(unsigned i = 0; i < 9; i++) std::cout << data.at(i) << " "; std::cout << data.at(9) << "." << std::endl; return 0; }
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 <= y '''then''' x : merge u (y:v)
'''else''' y : merge (x:u) v
[editovat] 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 se Mergesort také ukazuje být 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. V mnoha implementacích programovacích jazyků je Mergesort implicitním řadicím algoritmem (v Perlu 5.8, v Javě nebo v GNU C Library).
