Algoritmy řazení O(N logN)
(Založena nová stránka: 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, c...) |
|||
| Řádka 1: | Řádka 1: | ||
| + | // přidat ukázky | ||
| + | |||
Společné pro všechny: Řadíme stromem. | Společné pro všechny: Řadíme stromem. | ||
| − | Řazení haldou (heapsort) | + | == Řazení haldou (heapsort) == |
| − | Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, | + | |
| − | máme na poli | + | 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) | 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 | + | 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 | + | 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, | + | == 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 | 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. | |
| − | + | ||
| − | efektivní algoritmus, složitá analýza, nestabilní. | + | * 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 | 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) == | |
| − | v každém podstromu vzájemně vyměníme větší a menší prvky než pivot | + | |
| + | 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. | ||
| + | |||
| + | |||
| + | == Ř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 | 2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme | ||
| Řádka 40: | Řádka 56: | ||
Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu. | Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu. | ||
| − | Radix sort | + | Radix sort =??? |
Verze z 9. 8. 2011, 18:05
// přidat ukázky
Společné pro všechny: Řadíme stromem.
Obsah |
Ř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.
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
Ř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.
Ř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
Nestabilní metody lze "zestabilnit" například zpřeházením dat na vstupu.
Radix sort =???
