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.

Řešená úloha 1: 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á úloha 2: Merge sort řadí pole šesti čísel:

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

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

Řešená úloha 4: 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.

Úloha 5: 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 6: 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 7: 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 8: 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 9: Dokončete implementaci Heap sortu v Pythonu.

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

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

Úloha 11: 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 12: 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:

kde $n$ charakterizuje velikost problému.

Úloha 13: 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 14: 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 15: 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 16: Counting sortem řadíme pole čísel:

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

Jaké budou pro toto pole?

Úloha 17: Ř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 18: Ř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 19: 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 20: 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 21: 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 22: 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 23: 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 24: 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 25: 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 26: 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 27: 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 28: 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 29: 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é