Test na Porovnanie radiacich algoritmov a časová zložitosť

Otázka 1: Princíp rýchleho triedenia zahŕňa výber pivota a rozdelenie ostatných prvkov na dva podzoznamy podľa ich vzťahu k pivotu.

A. Áno

B. Nie

Vysvetlenie: Podľa princípu rýchleho triedenia (Quick Sort) sa vyberie jeden prvok ako pivot a ostatné prvky sa rozdelia na dva podzoznamy: tie, ktoré sú menšie ako pivot, a tie, ktoré sú väčšie ako pivot.

Otázka 2: V princípe bublinkového triedenia sa každý prvok porovnáva s prvým prvkom v zozname a následne sa vymení, ak je to potrebné, kým sa nenájde jeho správne miesto.

A. Áno

B. Nie

Vysvetlenie: Podľa princípu bublinkového triedenia sa neporovnáva každý prvok s prvým prvkom v zozname. Namiesto toho sa v každom prechode opakovane porovnáva každý prvok s jeho bezprostredným nasledovníkom a vymieňajú sa, ak sú v nesprávnom poradí, až kým sa v jednom prechode nevykoná žiadna výmena.

Otázka 3: Ktoré z nasledujúcich tvrdení o stabilite triediacich algoritmov je správne?

A. Stabilita algoritmu je dôležitá len pre číselné údaje.

B. Rýchle triedenie (Quick Sort) je stabilný triediaci algoritmus.

C. Bublinkové triedenie (Bubble Sort) a triedenie vkladaním (Insertion Sort) sú stabilné algoritmy.

D. Stabilný algoritmus môže zmeniť relatívne poradie rovnakých prvkov.

Vysvetlenie: Stabilný triediaci algoritmus zachováva relatívne poradie rovnakých prvkov. Podľa študijných materiálov sú Bublinkové triedenie a Triedenie vkladaním stabilné. Rýchle triedenie (Quick Sort) nie je stabilné. Stabilita je dôležitá, keď prvky majú okrem triediaceho kľúča aj iné atribúty, nie len pre číselné údaje.

Otázka 4: Ktoré z nasledujúcich tvrdení správne popisuje pamäťovú zložitosť algoritmu a jej vyjadrenie?

A. Pamäťová zložitosť popisuje, koľko dodatočnej pamäte algoritmus potrebuje, a vyjadruje sa pomocou notácie veľké O.

B. Triedenie s dodatočnou pamäťou znamená, že algoritmus vyžaduje konštantné množstvo dodatočnej pamäte, teda O(1).

C. Algoritmy s označením 'in-place triedenie' potrebujú pamäť úmernú veľkosti vstupu, napríklad O(n).

D. Merge Sort je príkladom algoritmu, ktorý vyžaduje pamäťovú zložitosť O(n) kvôli rekurzívnym volaniam.

Vysvetlenie: Pamäťová zložitosť algoritmu popisuje, koľko dodatočnej pamäte (okrem pamäte pre samotný vstup) algoritmus potrebuje na svoje vykonanie a vyjadruje sa pomocou notácie veľké O. Tvrdenie, že 'in-place triedenie' vyžaduje pamäť úmernú veľkosti vstupu O(n), je nesprávne, pretože in-place triedenie vyžaduje len konštantné množstvo dodatočnej pamäte O(1). Tvrdenie o triedení s dodatočnou pamäťou je tiež nesprávne, keďže to sú algoritmy vyžadujúce pamäť úmernú veľkosti vstupu (napr. O(n) alebo O(log n)), nie O(1). Napokon, Merge Sort vyžaduje pamäťovú zložitosť O(n) kvôli potrebe dodatočnej pamäte pre zlúčenie, nie primárne kvôli rekurzívnym volaniam ako je to u Quick Sortu v najhoršom prípade.

Otázka 5: Pre zachovanie pôvodného poradia rovnakých prvkov pri triedení nie je vždy nutné použiť stabilný algoritmus.

A. Áno

B. Nie

Vysvetlenie: Stabilita algoritmu je kľúčová, ak je dôležité zachovať pôvodné poradie duplikátov. Ak sa má zachovať pôvodné poradie rovnakých kľúčov, je nutné použiť stabilný algoritmus.