Test na Triedenie vkladaním (insertion sort)

Otázka 1: Premenná 'j' vo vnútornom cykle triedenia vkladaním sa zväčšuje o 1, aby sa posunula k predchádzajúcemu prvku v usporiadanej časti.

A. Áno

B. Nie

Vysvetlenie: Podľa podrobného algoritmu triedenia vkladaním sa v kroku 5 premenná 'j' zmenšuje o 1 (t.j., j = j - 1), aby sa posunula k predchádzajúcemu prvku v usporiadanej časti, nie zväčšuje.

Otázka 2: Máme pole [5, 2, 4, 6, 1, 3] a aplikujeme naň triedenie vkladaním (Insertion Sort) podľa uvedeného príkladu. Aký bude stav poľa po posunutí prvku A[2] = 5 doprava počas iterácie pre i = 4 (kľúč = 1)?

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

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

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

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

Vysvetlenie: Podľa príkladu v študijných materiáloch pre Iteráciu i = 4 (kľúč = 1) je počiatočný stav [2, 4, 5, 6 | 1, 3]. Najprv sa posúva A[3] = 6 doprava, výsledok je [2, 4, 5, _, 6 | 3]. Následne sa posúva A[2] = 5 doprava, čo vytvorí stav [2, 4, _, 5, 6, 3]. Voľné miesto vzniklo na indexe 2, kam sa neskôr vloží kľúč (1).

Otázka 3: Je algoritmus triedenia vkladaním stabilný?

A. Áno

B. Nie

Vysvetlenie: Algoritmus triedenia vkladaním je stabilný, pretože prvok 'kľúč' sa posúva len vtedy, ak je prvok v usporiadanej časti striktne väčší ako 'kľúč'. Ak sú si rovné, 'kľúč' sa vloží za existujúci rovnaký prvok, čím sa zachová ich pôvodné relatívne poradie.

Otázka 4: Triedenie vkladaním je vždy pomalé, a to aj pre malé dátové sady, pretože jeho časová zložitosť je vždy O(n²).

A. Áno

B. Nie

Vysvetlenie: Hoci najhoršia a priemerná časová zložitosť triedenia vkladaním je O(n²), nie je vždy pomalé. Pre malé dátové sady (typicky do niekoľkých desiatok prvkov) alebo takmer usporiadané dáta môže byť v praxi rýchlejšie ako zložitejšie algoritmy s lepšou asymptotickou zložitosťou kvôli menšej konštantnej réžii.

Otázka 5: Aká je priemerná časová zložitosť algoritmu triedenia vkladaním pre náhodne usporiadané pole?

A. O(n)

B. O(n²)

C. O(n log n)

D. O(log n)

Vysvetlenie: Pre náhodne usporiadané pole je priemerná časová zložitosť algoritmu triedenia vkladaním O(n²). V priemere sa každý kľúč musí posunúť cez polovicu už usporiadanej časti poľa, čo vedie ku kvadratickej časovej zložitosti.