Algoritmy řazení O(N logN)
// přidat ukázky
Společné pro všechny: Řadíme stromem.
Obsah |
[editovat] Řazení haldou (heapsort)
Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tři, čtyři atd. prvky, až máme na poli vytvořenu haldu. Následně zaměníme nejvyšší prvek (vyjmeme ho) s posledním a obnovíme vlastnost haldy na n−1 prvcích. Obnovení haldy je O(log n) a obnovujeme po každém výběru, tedy O(n log2n) To opakujeme až zbude jednoprvková halda a celé pole je seřazené. Nestabilní (složitost závisí na vstupních datech).
V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme.
Hezká vizualizace: http://varkor.com/mathematics/heapsort/?0,1,1,2,3,5,8,13,21,34,55,89,144,233
[editovat] Shellovo řazení (shellsort)
Posloupnost rozdělíme na podposloupnosti s krokem h (každý h-tý počínaje prvním, počínaje druhým až počínaje h − 1-ním), které nezávisle seradíme vkládáním (insertsortem). Následne snižujeme hodnotu h a provádíme totéž až do serazení s h = 1. Prvky daleko od své výsledné pozice se k ní dostanou v menším počtu kroků, než u obyčejného insertsortu.
- Shell - počátecní h = polovina délky pole, snížení vydělením dvěma
- Knuth - posloupnost 3i + 1, počáteční h = její prvek v nejbližší třetině délky pole
Jednoduchý a efektivní algoritmus, složitá analýza, nestabilní.
V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec
Poměrně zajímavě udělaná ukázka z kartama: http://www.youtube.com/watch?v=QG8hs0wqmqk
[editovat] Řazení dělením (splitsort, quicksort)
Určíme prvek, jehož hodnota bude rozdělovat pole (pivot). Procházíme z obou stran pole a menší hodnoty vpravo prohazujeme s vetšími vlevo, až se oba průchody potkají. Na tuto pozici přesuneme pivot - vlevo jsou hodnoty menší, vpravo vetší. Totéž provedeme s částí pole vlevo od pivotu i vpravo od nej. Rekurze končí, je-li předán pouze jeden prvek k seřazení. Nejčasteji se pivot určuje jako krajní prvek pole (nezasahuje pak do procesu dělení). Lze použít zásobník místo rekurze. Snadno implementovatelné, nestabilní.
V kostce: rozdělení do stromu podle pivotů (prvek velikostně cca uprostřed podstromu, ideálně medián, ale může být i náhodný), v každém podstromu vzájemně vyměníme větší a menší prvky než pivot.
Výukové videjko: http://www.youtube.com/watch?v=y_G9BkAm6B8
[editovat] Řazení slucováním (mergesort)
Pole je rekurzivně rozdělováno na poloviny. Dojdeme až na úroveň dvojic prvku, které seřadíme (sloučíme). O úroven výše opět po dvojicích sloučíme (kopírujeme vždy menší prvek z obou polí a posuneme se za nej) a postupujeme až sloučíme obě poloviny původního pole. Je to nejčasteji používaná metoda a je stabilní.)
V kostce: jako když mícháme karty - 2 balíčky a děláme 
???????
. Procházíme 2 podstromy a řadíme posunem 2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme
Bezva video - http://www.youtube.com/watch?v=GCae1WNvnZM
Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu.
Radix sort =???
