8 - Řazení $O(n \log n)$

Přednáška 8 v oddíle Přednášky. Pro implementační detaily koukněte do přednášky, zde jen popíšeme základní myšlenky.

Halda (Heap) je binární strom, kde platí pravidlo, že klíče v obou potomcích jsou vyšší (nebo rovni) než v jejich rodiči. Haldu lze zapsat do pole, které reprezentuje úplný strom. Někdy se specifikuje jako min-heap, protože v kořeni je minimum. Alternativně můžeme sestrojit max-heap, kde je v kořeni maximum a potomci jsou vždy menší (nebo rovni).

insert: Pokud přidáváme prvek, vložíme ho na konec pole a “probubláváme” ho nahoru skrze strom, dokud má klíč v rodiči větší hodnotu.

deleteTop: Pokud odebíráme kořen (jiné prvky neodebíráme), nahradíme ho posledním prvkem z haldy a opravujeme haldu směrem dolů, záměnou za menšího (pro min-heap) z jeho potomků (pokud je menší než klíč v rodiči.

Haldu lze využít (kromě heap sortu) také na prioritní frontu.

Nejprve upravíme pole tak aby reprezentovalo haldu (heapify) - tato akce lze provést se složitostí $\Theta(n)$.

Pak postupně odebíráme kořen a dáváme ho do pole za poslední prvek haldy. Toto je $n$ krát operace se složitostí $\Theta(\log n)$. Celkem $\Theta(n + n \log n) = \Theta(n \log n)$

Pokud použijeme min-heap, pole bude seřazené sestupně, pokud max-heap, bude seřazené vzestupně.

Přístup ve stylu “rozděl a panuj”. Algoritmus funguje tak, že rozdělíme pole na 2 díly, rekurzivně je seřadit a pak spojit (merge) dané díly v lineárním čase.

Hloubka stromu rekurzivních volání je $\log n$ a na každé úrovni provádíme merge na $n$ prvcích. Celkově tedy $\Theta(n \log n)$.

Merge sort je stabilní, na rozdíl od Heap sortu.

Prohlédněte si vizuální animované srovnání řadících algoritmů.

Pokud pouze porovnáváme prvky po dvojicích, není možné řadit je asymptoticky rychleji než $\Theta(n \log n)$. Proto potřebujeme jiné znalosti o datech.

Toto řazení je vhodné pro prvky, kde jsou duplikáty a jsme schopni enumerovat všechny prvky (typicky vhodná jsou celá čísla). Najdeme minimum a maximum, pak procházíme prvky v rozsahu hodnot a počítáme četnosti jednotlivých prvků. Poté je přesuneme prvky v novém pořadí, podle předpočítaných četností. Asymptotická složitost je $\Theta(n + c)$ kde $c$ je rozsah prvků v poli pro které počítáme četnosti.

Někdy nazývané přihrádkové řazení, spočívá v tom, že řadíme řetězce stejné délky nad omezenou abecedou znak po znaku. Na jednom znaku řadíme pak lineárně, podobně jako counting sort. Pro sestavení pořadí řetězců poté projdeme abecedu znak po znaku a přesouváme řetězce pro daný znak podle uloženého pořadí.

Asymptotickou složitost má radix sort $\Theta(n \cdot l + A \cdot l)$ kde $l$ je délka řetězců, a $A$ je počet znaků (pro zisk pořadí po každém průchodu musíme procházet všechny znaky).

Řešená úloha 1: Která z následujících posloupností představuje (min-)haldu uloženou v poli?

a) 9 5 4 6 3
b) 5 4 2 3 9
c) 3 8 9 5 6
d) 5 1 8 9 1
e) 1 3 6 5 4

Řešení (rozbalit)

Řešená úloha 2: Zadanou posloupnost seřaďte pomocí heap sortu. Registrujte stav v poli po každém kroku. Nejprve po každé opravě částečné haldy od prostředku pole směrem k začátku, tj. při první fázi. Potom také po každé opravě haldy a přenesení prvku z vrcholu haldy za konec haldy.

Řešení (rozbalit)

Řešená úloha 3: Merge sort řadí pole šesti čísel:

Jak bude toto pole vypadat před provedením poslední operace merge?

Řešení (rozbalit)

Řešená úloha 4: Counting sortem seřaďte pole čísel:

Řešení (rozbalit)

Řešená úloha 5: Následující posloupnost řetězců je nutno seřadit pomocí Radix Sortu (přihrádkového řazení). Proveďte všechny průchody algoritmu daným polem a zapište stavy pomocných polí po každém průchodu.

Řešení (rozbalit)

Úloha 6: Které z následující posloupností představují (min-)haldu o čtyřech prvcích uloženou v poli?

a) 1 3 4 2
b) 1 4 2 3
c) 1 2 4 3
d) 2 3 4 1
e) 1 3 2 4

Úloha 7: Pole $n$ prvků uspořádané v rostoucím pořadí lze považovat za haldu. Z této operace odstraníme standardní operací deleteTop() její vrchol. Určete za jakých okolností je možné, aby výsledné pole bylo po uvedené operaci opět celé uspořádané.

Úloha 8: V haldě, jejíž vrchol obsahuje minimální prvek haldy, máme najít prvek s maximálním klíčem. Jaká je asymptotická složitost této akce? Umíte vyřešit problém lépe (ne nutně asymptoticky) než v $n$ operacích.

Úloha 9: Je dáno $n$ ($n \in \mathbb{N}, n \ge 2$) navzájem různých celočíselných klíčů a prázdná halda. Všechny klíče vložíme jeden po druhém v náhodném pořadí do dané haldy.

1. Jaká je asymptotická složitost tohoto procesu?
2. Je možné, že pro některé speciální pořadí klíčů bude asymptotická složitost menší nebo větší než v náhodném případě?

Úloha 10: Z binární haldy obsahující $n^3$ prvků, jejíž kořen obsahuje nejmenší hodnotu z celé haldy, odstraníme $n$ nejmenších prvků. Jaká je asymptotická složitost této akce?

Úloha 11: Do binární haldy obsahující $n^{1.5}$ prvků, jejíž kořen obsahuje nejmenší hodnotu z celé haldy, přidáme $n$ prvků. Jaká je asymptotická složitost této akce?

Úloha 12: Danou haldu s $n$ prvky máme rozdělit na dvě haldy, tak že každá bude mít $n/2$ prvků. Předpokládejme, že původní halda je uložena v poli délky $n$ a nové haldy budou uloženy ve dvou připravených polích délky $n/2$. Navrhněte, jak rozdělit haldu v čase $\Theta(n)$.

Úloha 13: Je dána halda uložená v poli. Proveďte první krok fáze řazení v Heap sortu.

Nyní proveďte to samé pro tuto haldu:

Úloha 16: Heap sort

a) není stabilní, protože halda (heap) nemusí být pravidelným stromem
b) není stabilní, protože žádný rychlý algoritmus ($\Theta(n \cdot \log n)$) nemůže být stabilní
c) je stabilní, protože halda (heap) je vyvážený strom
d) je stabilní, protože to zaručuje pravidlo haldy
e) neplatí o něm ani jedno předchozí tvrzení

Úloha 15: Vysvětlete, jak je nutno modifikovat Heap sort, aby po jeho skončení pole obsahovalo prvky seřazené vzestupně. Algoritmus musí být stejně rychlý, nejen asymptoticky, a nesmí používat žádné další datové struktury nebo proměnné.

Úloha 16: Předložíme-li Heap sort-u vzestupně seřazenou posloupnost délky $n$, bude složitost celého řazení

a) $\Theta(n)$, protože Heap sort vytvoří haldu v čase $\Theta(n)$
b) $\Theta(n^2)$, protože Heap sort vytvoří haldu v čase $\Theta(n^2)$
c) $\Theta(n \cdot \log_2 n)$, protože je to složitost vytvoření haldy
d) $\Theta(n \cdot \log_2 n)$, protože je to složitost zpracování haldy
e) $\Theta(n)$, protože vytvoření i zpracování haldy bude mít právě tuto složitost

Úloha 17: Dokončete implementaci Heap sortu v Pythonu.

Úloha 18: Merge sort řadí pole šesti čísel:

Jak bude toto pole vypadat před provedením poslední operace merge?

Úloha 19: Merge sort

a) lze napsat tak, aby nebyl stabilní
b) je stabilní, protože jeho složitost je $\Theta(n \cdot \log n)$
c) je nestabilní, protože jeho složitost je $\Theta(n \cdot \log n)$
d) je rychlý ($\Theta(n \cdot \log n)$) právě proto, že je stabilní
e) neplatí o něm ani jedno předchozí tvrzení

Úloha 20: S použitím $\Theta$/$O$/$\Omega$ symboliky vyjádřete asymptotickou složitost Merge sortu nad daným polem v závislosti na hodnotě $n$. Výsledný vztah předložte v co nejjednodušší podobě.

Pole má velikost:

1. $2n - 2$
2. $2n^3$
3. $2n^3 + \log n$

kde $n$ charakterizuje velikost problému.

Úloha 21: Jaká je asymptotická složitost algoritmu zvaného 4-way merge sort. Algoritmus funguje jako standardní merge sort, pouze pole rozkládá na 4 části místo dvou.

Úloha 22: Implementujte nerekurzivní variantu Merge sortu s využitím vlastního zásobníku. Vaše implementace nemusí usilovat o maximální rychlost, stačí, když dodrží asymptotickou složitost Merge sortu. Můžete využít rekruzivní implementaci Merge sortu v Pythonu.

Úloha 23: Merge Sort lze naprogramovat bez rekurze („zdola nahoru“) také tak, že nejprve sloučíme jednotlivé nejkratší možné úseky, pak sloučíme delší úseky atd. Proveďte to. Můžete využít rekruzivní implementaci Merge sortu v Pythonu.

Úloha 24: Counting sortem řadíme pole čísel:

Jaký bude nejmenší a největší index v poli četností?

Jaké budou pro toto pole?

Úloha 25: Řadíme 14 celých čísel. Těsně předtím, než se začne plnit výstupní pole v Counting sortu, je obsah původního pole četností následující:

Napište, jak vypadá výsledné uspořádané pole, za předpokladu, že všechna pole začínají indexem 1.

Úloha 26: Řadíme 15 celých čísel. Těsně předtím, než se začne plnit výstupní pole v Counting sortu, je obsah původního pole četností následující:

Napište, jak vypadá výsledné uspořádané pole, za předpokladu, že všechna pole začínají indexem 1.

Úloha 27: Uvažujme pole obsahující 1000 navzájem různých čísel v pohyblivé řádové čárce. Counting sort se pro toto pole

a) hodí, protože toto řazení má lineární složitost
b) hodí, protože toto řazení má sublineární složitost
c) hodí, protože čísla lze převést na řetězce
d) nehodí, protože čísla v poli nemusí být celá
e) nehodí, protože čísla jsou navzájem různá

Úloha 28: Na začátku Counting sortu je v poli četností uložena právě četnost výskytu každé hodnoty ve vstupním poli. V průběhu řazení se obsah pole četností průběžně mění.

Rozhodněte, zda je možno po dokončení celého řazení rekonstruovat z modifikovaného pole četností původní (a ovšem i výsledné) četnosti jednotlivých řazených hodnot.

Úloha 29: Následující posloupnost řetězců je nutno seřadit pomocí Radix Sortu (přihrádkového řazení). Proveďte první průchod (z celkových čtyř průchodů) algoritmu danými daty a napište, jak budou po tomto prvním průchodu seřazena.

Proveďte to samé pro následující posloupnosti:

Úloha 30: Radix sort řadí dané pole řetězců. Napište, jak budou zaplněna jednotlivá pomocná pole (z, k, d, podle přednášky) po prvním průchodu algoritmu, tj. po seřazení podle posledního znaku.

Jak budou zaplněna pro následující posloupnost?

Úloha 31: Radix sort právě řadí podle 3. znaku od konce a ještě průchod nedokončil. Jak se bude postupně měnit obsah polí po zařazení každého z dalších řetězců?

abbac (9), aaaaa (4), bbbac (6)

Čísla v závorkách uvádějí pozici řetězce ve vstupním poli. Aktuální obsah polí je

Úloha 32: Radix sort právě řadí podle 4. znaku od konce a ještě průchod nedokončil. Jak se bude postupně měnit obsah polí po zařazení každého z dalších řetězců?

baaab (11), ccaba (4), ababa (6), babab (5), bbbbc (10)

Čísla v závorkách uvádějí pozici řetězce ve vstupním poli. Aktuální obsah polí je

Úloha 33: Pomocí Radix sortu řadíme pole $n$ řetězců, každý řetězec má kladnou délku k. Asymptotická složitost tohoto řazení je

a) $\Theta(k^2)$
b) $\Theta(n^2)$
c) $\Theta(kn)$
d) $\Theta(n \cdot \log n)$
e) $\Theta(kn \cdot \log n)$

Úloha 34: Pole A obsahuje téměř seřazené řetězce (např. z 99% seřazené), pole B obsahuje řetězce stejné délky, ale zcela neseřazené. Radix sort seřadí asymptoticky

a) A rychleji než B
b) B rychleji než A
c) A stejně rychle jako B, použije více paměti pro řazení A
d) A stejně rychle jako B, použije více paměti pro řazení B
e) A stejně rychle jako B a použití paměti bude stejné

Úloha 35: Každé kladné číslo typu int lze interpretovat jako posloupnost čtyř znaků reprezentujích jeho zápis v soustavě o základu $256$. Jinými slovy, hodnotu každého Bytu tohoto čísla bude považovat za samostatný znak. Například číslo $1697043971$ se rovná $101 \cdot 256^3 + 38 \cdot 256^2 + 214 \cdot 256^1 + 3 \cdot 256^0$, takže jej lze v tomto návrhu zapsat jako $101$ $38$ $214$ $3$, kde každé číslo interpretujeme jako samostatný symbol.

Jak je nutno modifikovat Radix sort, aby mohl řadit pole takto interpretovaných celých čísel?

Bude to časově/paměťově výhodné? Pro jak veliká pole?

Úloha 36: Kterou následující dvojici řazení je možno implementovat tak, aby byla stabilní?

a) Heap sort a Insertion sort
b) Selection sort a Quick sort
c) Insertion sort a Merge sort
d) Heap sort a Merge sort
e) Radix sort a Quick sort

Úloha 37: Poskytneme-li Quick sortu (Q) a Merge sortu (M) stejná data k seřazení, platí

a) Q bude vždy asymptoticky rychlejší než M
b) M bude vždy asymptoticky rychlejší než Q
c) někdy může být Q asymptoticky rychlejší než M
d) někdy může být M asymptoticky rychlejší než Q
e) Q i M budou vždy asymptoticky stejně rychlé