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...) |
(→Řazení haldou (heapsort)) |
||
| (Není zobrazeno 6 mezilehlých verzí od 2 uživatelů.) | |||
| Řá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) | + | Hezká vizualizace: http://varkor.com/mathematics/heapsort/?0,1,1,2,3,5,8,13,21,34,55,89,144,233 |
| − | 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) | + | Poměrně zajímavě udělaná ukázka z kartama: http://www.youtube.com/watch?v=QG8hs0wqmqk |
| − | + | ||
| − | vpravo prohazujeme s vetšími vlevo, až se oba | + | == Řazení dělením (splitsort, quicksort) == |
| − | hodnoty menší, vpravo vetší. Totéž provedeme s | + | |
| − | je-li | + | Určíme prvek, jehož hodnota bude rozdělovat pole (pivot). Procházíme z obou stran pole a menší hodnoty |
| − | do procesu | + | 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 | ||
| + | |||
| + | == Ř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 [[Soubor:Mergesort.jpg]] | |
| − | + | ??????? | |
| − | + | . 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 | ||
| + | Bezva video - http://www.youtube.com/watch?v=GCae1WNvnZM | ||
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 =??? |
| + | [[Kategorie:fav-kiv-bzinf]] | ||
Aktuální verze z 4. 6. 2016, 07:30
// 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 =???
