Test na Rýchle triedenie (quicksort)

Otázka 1: Po kroku 'Rozdeľ' (Divide) v algoritme Quicksort sa pivot nachádza na svojej konečnej pozícii v utriedenom poli.

A. Áno

B. Nie

Vysvetlenie: Podľa princípu algoritmu Quicksort, v kroku 'Rozdeľ' sa pole rozdelí na podpolia vzhľadom na pivot, pričom pivot sa po tomto kroku už nachádza na svojej konečnej pozícii v utriedenom poli.

Otázka 2: Rýchle triedenie (Quicksort) triedi prvky bez porovnávania ich hodnôt.

A. Áno

B. Nie

Vysvetlenie: Rýchle triedenie (Quicksort) patrí medzi porovnávacie triediace algoritmy, čo znamená, že triedi prvky porovnávaním ich hodnôt.

Otázka 3: V Lomutoho schéme rozdelenia, ak je počas prechodu poľom prvok `A[j]` väčší ako vybraný pivot, aká akcia sa vykoná?

A. Prvky `A[i]` a `A[j]` sa vymenia.

B. Index `i` sa zvýši o 1.

C. Prvok `A[j]` zostáva na svojej pozícii a index `j` pokračuje k ďalšiemu prvku bez vykonania výmeny s `A[i]`.

D. Pole sa okamžite rozdelí na dve časti.

Vysvetlenie: Podľa Lomutoho schémy rozdelenia, v kroku 4 je uvedené: 'Ak je `A[j]` menšie alebo rovné pivotu: a. Zvýši sa `i` o 1. b. Vymenia sa prvky `A[i]` a `A[j]`.' To znamená, že ak `A[j]` NIE JE menšie alebo rovné pivotu (t.j. je väčšie ako pivot), neprebieha žiadna výmena s `A[i]` a index `i` sa nezvyšuje. Prechod jednoducho pokračuje na ďalší prvok s indexom `j`.

Otázka 4: Ktoré tvrdenia správne popisujú princíp algoritmu 'Rozdeľ a panuj' (Divide and Conquer) v kontexte Quicksortu?

A. V kroku 'Rozdeľ' sa pole rozdelí na podpolia, kde všetky prvky menšie ako pivot sú v ľavom podpoli a všetky prvky väčšie ako pivot sú v pravom podpoli.

B. Krok 'Panuj' zahŕňa rekurzívnu aplikáciu rýchleho triedenia na vytvorené podpolia.

C. Krok 'Spoj' je netriviálny a vyžaduje dodatočné operácie na zlúčenie utriedených podpolí.

D. Pivot po kroku 'Rozdeľ' nie je na svojej konečnej pozícii a musí byť dodatočne utriedený.

Vysvetlenie: Princíp algoritmu 'Rozdeľ a panuj' v Quicksorte spočíva v kroku 'Rozdeľ', kde sa vyberie pivot a pole sa rozdelí na dve podpolia podľa hodnôt menších a väčších ako pivot. Krok 'Panuj' rekurzívne aplikuje triedenie na tieto podpolia. Krok 'Spoj' je triviálny, pretože pivot je už na správnej pozícii a podpolia sú po rekurzii utriedené.

Otázka 5: Základný prípad rekurzie pre algoritmus Quicksort nastáva, keď podpole obsahuje 2 prvky.

A. Áno

B. Nie

Vysvetlenie: Základný prípad rekurzie pre Quicksort je situácia, keď podpole obsahuje 0 alebo 1 prvok, pretože takéto podpole je už utriedené.