Test na Řazení vkládáním (insertion sort)

Otázka 1: V pseudokódu algoritmu řazení vkládáním je klíč (klíč) po dokončení vnitřního cyklu 'ZATÍMCO' (WHILE) vložen na pozici 'A[j + 1]'.

A. Ano

B. Ne

Vysvětlení: Podle pseudokódu algoritmu řazení vkládáním je poslední krok po ukončení vnitřního cyklu 'ZATÍMCO' (WHILE) příkaz 'A[j + 1] = klíč', který vkládá hodnotu klíče na správné místo v seřazené části pole.

Otázka 2: Prostorová složitost řazení vkládáním je lineární, tedy O(n).

A. Ano

B. Ne

Vysvětlení: Prostorová složitost řazení vkládáním je konstantní, O(1), protože k řazení nepotřebuje žádný dodatečný paměťový prostor kromě několika proměnných.

Otázka 3: Máme pole čísel `[5, 2, 4, 6, 1, 3]`. Po zpracování prvních tří prvků (klíč=5, klíč=2, klíč=4) se pole nachází ve stavu `[2, 4, 5 | 6, 1, 3]`. Jak bude pole vypadat bezprostředně po dokončení zpracování čtvrtého prvku (klíč = 6) podle algoritmu řazení vkládáním?

A. [2, 4, 5, 6, 1, 3]

B. [1, 2, 4, 5, 6, 3]

C. [2, 4, 6, 5, 1, 3]

D. [2, 5, 4, 6, 1, 3]

Vysvětlení: Podle Krok 4 příkladu: V aktuálním stavu je pole `[2, 4, 5 | 6, 1, 3]`, kde klíč je 6. Porovnáme 6 s 5. Jelikož 6 > 5, 6 je již na správném místě vzhledem k 5 a není potřeba žádný posun. Klíč 6 se tak jednoduše ponechá na své pozici. Pole po vložení (nebo v tomto případě ponechání na místě) je `[2, 4, 5, 6 | 1, 3]`. Ostatní možnosti neodpovídají postupu řazení vkládáním pro tento konkrétní krok.

Otázka 4: Jaká je časová složitost algoritmu řazení vkládáním (Insertion Sort) v nejlepším, nejhorším a průměrném případě?

A. Nejlepší O(n), Nejhorší O(n²), Průměrný O(n²)

B. Nejlepší O(n log n), Nejhorší O(n²), Průměrný O(n log n)

C. Nejlepší O(n), Nejhorší O(n), Průměrný O(n²)

D. Nejlepší O(n²), Nejhorší O(n²), Průměrný O(n²)

Vysvětlení: Dle studijních materiálů je časová složitost řazení vkládáním v nejlepším případě (již seřazené pole) O(n), protože algoritmus provede pouze jedno porovnání pro každý prvek. V nejhorším případě (pole seřazené v opačném pořadí) je časová složitost O(n²), jelikož je potřeba pro každý prvek provést porovnání se všemi předchozími a posunout je. Průměrný případ pro náhodně uspořádané pole má také časovou složitost O(n²).

Otázka 5: Experimentování s různými počátečními stavy pole v simulaci řazení vkládáním neumožňuje studentům pozorovat změny v počtu kroků potřebných k dokončení řazení.

A. Ano

B. Ne

Vysvětlení: Simulace řazení vkládáním umožňuje studentům experimentovat s různými počátečními stavy pole (např. náhodné, seřazené, obráceně seřazené) a pozorovat, jak se mění rychlost a počet kroků potřebných k dokončení řazení. To je klíčové pro pochopení konceptů nejlepšího a nejhoršího případu.