Algoritmy řazení O(N logN)
Společné pro všechny: Řadíme stromem.
Řazení haldou (heapsort) Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tri, ctyri atd. prvky, až máme na poli vytvorenu haldu. Následne zamení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 serazené. 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
Shellovo řazení (shellsort) Posloupnost rozdělíme na podposloupnosti s krokem h (každý h-tý počínaje prvním, pocínaje druhým až pocí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 poctu kroku, než u obycejného insertsortu. Shell - pocátecní h = polovina délky pole, snížení vydelením dvema; Knuth - posloupnost 3i + 1, pocátecní h = její prvek nejbližší tretine 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
Řazení dělením (splitsort, quicksort) Urcíme prvek, jehož hodnota bude rozdelovat pole (pivot). Procházíme z obou stran pole a menší hodnoty vpravo prohazujeme s vetšími vlevo, až se oba pruchody potkají. Na tuto pozici presuneme pivot - vlevo jsou hodnoty menší, vpravo vetší. Totéž provedeme s cástí pole vlevo od pivotu i vpravo od nej. Rekurze koncí, je-li predán pouze jeden prvek k serazení. Nejcasteji se pivot urcuje jako krajní prvek pole (nezasahuje pak do procesu delení). Lze použít zásobník místo rekurze. Snadno implementovatelné, nestabilní.
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
Řazení slucováním (mergesort) Pole je rekurzivne rozdelováno na poloviny. Dojdeme až na úroven dvojic prvku, které seradíme (sloucíme). O úroven výše opet po dvojicích sloucíme (kopírujeme vždy menší prvek z obou polí a posuneme se za nej) a postupujeme až sloucíme obe poloviny puvodního pole. Je to nejcasteji 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
Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu.
Radix sort
