11 Triedenia

1. Čo je problém triedenia v informatike?

Usporiadanie prvkov podľa kľúča do definovaného poradia.

2. Čo je kľúč pri triedení?

Hodnota podľa ktorej sa prvky porovnávajú a usporadúvajú.

3. Aký je rozdiel medzi vnútorným a vonkajším triedením?

Vnútorné prebieha v pamäti, vonkajšie na disku.

4. Aké sú hlavné miery zložitosti triedenia?

Čas a pomocná pamäť.

5. Čo je základná operácia pri triedení porovnávaním?

Porovnanie dvoch prvkov.

6. Prečo analyzujeme počet porovnaní?

Je hlavnou mierou efektívnosti.

7. Čo je rozhodovací strom triediaceho algoritmu?

Strom reprezentujúci všetky možné porovnania.

8. Čo reprezentuje cesta v rozhodovacom strome?

Jeden konkrétny priebeh algoritmu.

9. Čo reprezentujú listy rozhodovacieho stromu?

Permutácie vstupných prvkov.

10. Koľko listov musí mať strom pre n prvkov?

Aspoň n!.

11. Aký je dolný odhad počtu porovnaní triedenia?

Ω(n log n).

12. Prečo existuje dolná hranica Ω(n log n)?

Kvôli počtu možných permutácií.

13. Čo znamená, že algoritmus je optimálny?

Dosahuje dolnú hranicu zložitosti.

14. Čo je Insertion Sort (priamym vkladaním)?

Postupné vkladanie prvkov do utriedenej časti.

15. Aká je časová zložitosť Insertion Sort v najhoršom prípade?

O(n²).

16. Aká je časová zložitosť Insertion Sort v najlepšom prípade?

O(n).

17. Prečo je Insertion Sort rýchly na takmer utriedených dátach?

Má málo presunov.

18. Je Insertion Sort stabilný?

Áno.

19. Čo znamená stabilita triedenia?

Zachováva poradie rovnakých prvkov.

20. Čo je Binary Insertion Sort?

Insertion Sort s binárnym vyhľadávaním.

21. Zlepšuje Binary Insertion Sort celkovú zložitosť?

Nie, stále O(n²).

22. Prečo Binary Insertion Sort nepomáha výrazne?

Presuny prvkov zostávajú O(n²).

23. Čo je Selection Sort (priamy výber)?

Opakovane vyberá minimum a dáva ho na začiatok.

24. Aká je časová zložitosť Selection Sort?

O(n²) vždy.

25. Prečo je Selection Sort neefektívny?

Vždy robí rovnaký počet porovnaní.

26. Koľko presunov robí Selection Sort?

O(n).

27. Čo je Bubble Sort?

Vymieňa susedné prvky, najväčší „vypláva“ hore.

28. Aká je časová zložitosť Bubble Sort?

O(n²).

29. Prečo je Bubble Sort neefektívny?

Veľa zbytočných porovnaní.

30. Čo je Merge Sort?

Algoritmus rozdeľ-utrid-zlúč.

31. Aká je časová zložitosť Merge Sort?

O(n log n).

32. Prečo je Merge Sort efektívny?

Rozdeľuje problém na polovice.

33. Aká je nevýhoda Merge Sort?

Potrebuje pomocnú pamäť.

34. Čo znamená „zlúčenie“ v Merge Sort?

Spojenie dvoch utriedených častí.

35. Čo je Heap Sort?

Triedenie pomocou haldy.

36. Aká je časová zložitosť Heap Sort?

O(n log n).

37. Aká je výhoda Heap Sort?

Nepotrebuje pomocnú pamäť.

38. Čo je Quicksort?

Algoritmus založený na delení podľa pivotu.

39. Ako funguje Quicksort?

Rozdelí pole na menšie a väčšie prvky než pivot.

40. Aká je časová zložitosť Quicksort v najlepšom prípade?

O(n log n).

41. Aká je časová zložitosť Quicksort v najhoršom prípade?

O(n²).

42. Kedy nastáva najhorší prípad Quicksortu?

Pri zlom výbere pivotu.

43. Prečo je Quicksort v praxi rýchly?

Má dobrý priemerný výkon.

44. Aká je priemerná zložitosť Quicksortu?

O(n log n).

45. Čo je pivot v Quicksorte?

Prvok, podľa ktorého delíme pole.

46. Aký je rozdiel medzi Merge Sort a Quicksort?

Merge Sort používa pamäť, Quicksort nie.

47. Ktorý algoritmus je stabilný: Merge Sort alebo Heap Sort?

Merge Sort.

48. Prečo je dôležitý výber algoritmu triedenia?

Závisí od dát a požiadaviek.

49. Ktoré triedenia majú zložitosť O(n²)?

Insert, Selection, Bubble.

50. Ktoré triedenia majú zložitosť O(n log n)?

Merge Sort, Heap Sort, Quicksort (priemerne).