Test na Rychlé řazení (quicksort)
Rychlé řazení (Quicksort): Podrobný průvodce pro studenty
Test: Algoritmus rychlého řazení (Quicksort), Lomutovo dělení Quicksortu, Algoritmus Quicksort
20 otázek
Otázka 1: Po rekurzivním seřazení podpolí v algoritmu Quicksort je nutné provést dodatečný krok sloučení pro spojení výsledků.
A. Ano
B. Ne
Vysvětlení: Podle principu rychlého řazení se pivot po rozdělení pole nachází na své konečné seřazené pozici. Následně je algoritmus rekurzivně aplikován na podpole prvků menších než pivot a na podpole prvků větších než pivot. Materiály neuvádějí žádný dodatečný krok sloučení (merge) podpolí; podpole jsou řazena in-place kolem již umístěného pivota, což znamená, že po dokončení rekurze je celé pole seřazeno.
Otázka 2: Při použití Lomutova dělení (Lomuto Partition Scheme) v algoritmu Quicksort, co se stane, pokud je prvek `A[j]` menší nebo roven zvolenému pivotu během průchodu polem?
A. Ukazatel `i` se dekrementuje a prvek `A[i]` se vymění s pivotem.
B. Ukazatel `j` se inkrementuje a prvek `A[j]` se přesune na začátek pole.
C. Ukazatel `i` se inkrementuje a prvky `A[i]` a `A[j]` se vymění.
D. Nic se nestane, prvek `A[j]` zůstane na své pozici a pokračuje se v průchodu.
Vysvětlení: Podle popisu Lomutova dělení, pokud je prvek `A[j]` menší nebo roven pivotu, pak se inkrementuje ukazatel `i` a následně se vymění prvky `A[i]` a `A[j]`. Tím se `A[j]` přesune do 'menší' části pole, která je sledována ukazatelem `i`.
Otázka 3: Nejhorší časová složitost algoritmu Quicksort je O(n²), což nastává, když volba pivota vždy vede k extrémně nevyváženému dělení.
A. Ano
B. Ne
Vysvětlení: Nejhorší časová složitost Quicksortu je O(n²). Tento případ nastává, když volba pivota vždy vede k extrémně nevyváženému dělení, například pokud je pivotem vždy nejmenší nebo největší prvek v podpoli.
Otázka 4: V pseudokódu funkce `rozdel_pole` je proměnná `i` inicializována na hodnotu `začátek`.
A. Ano
B. Ne
Vysvětlení: Podle pseudokódu funkce `rozdel_pole` je proměnná `i` inicializována na `začátek - 1`, nikoli na `začátek`.
Otázka 5: Podle studijních materiálů, jaká je konečná pozice pivota v Lomutově dělení po dokončení dělicího procesu a výměně pivota?
A. Index `i` před provedením finální výměny s pivotem.
B. Index `i + 1` po dokončení hlavní smyčky a finální výměně s pivotem.
C. Index posledního prvku podpole, ze kterého byl pivot původně zvolen.
D. Vždy střední index děleného podpole.
Vysvětlení: Studijní materiály explicitně uvádějí: 'Vraťte index `i + 1`, což je konečná pozice pivota.' Příklad dále ukazuje, že po dokončení cyklu se vymění `A[i + 1]` s pivotem, což zajistí, že pivot je na správné pozici `i + 1`.