Programovanie (1) v C/C++ FMFI UK, Prednáška 11, 28.10.2020

Zhrnutie prednášky

Prednáška najprv oznamuje organizačné veci: zadanie druhej domácej úlohy o prehľadávaní s návratom, pravidlá samostatnej práce a trest za opisovanie, váhu úloh (spolu 15 % známky) a pravidlo mínus 5 bodov za týždeň bez vyriešeného príkladu. Od budúceho týždňa nastúpi nový prednášajúci a začne téma práca s pamäťou. Hlavná časť predstavuje princíp rozdeľuj a panuj (rozdelenie, rekurzívne riešenie podproblémov, spojenie riešení) na triedení Merge Sort. Pole sa rozseká v strede, každá polovica sa rekurzívne utriedi a potom sa dve utriedené postupnosti spoja zlučovaním (merge), čo je jediná náročná časť algoritmu. Rekurzívna funkcia dostáva ľavý a pravý okraj úseku, triviálny prípad je úsek s nanajvýš jedným prvkom. Na konci sa má prejsť aj ku Quick Sortu a dokončiť prehľadávanie s návratom.

• - Domáca úloha 2 sa týka prehľadávania s návratom; úlohy treba robiť samostatne, za opisovanie hrozí 0 bodov všetkým zúčastneným.
• - Tri domáce úlohy tvoria 15 % známky; za týždeň bez vyriešeného príkladu na cvičení hrozí mínus 5 bodov.
• - Pri práci s poľom treba kontrolovať hranice indexov (napr. i-1 pri i = 0 alebo i+1 mimo veľkosti poľa).
• - Bubble Sort, Insertion Sort a Max Sort majú kvadratickú zložitosť O(n²), preto sa pre veľké polia nepoužívajú.
• - Princíp rozdeľuj a panuj má tri fázy: rozdeliť problém, rekurzívne vyriešiť podproblémy, spojiť riešenia.
• - Merge Sort rozdelí pole v strede, rekurzívne utriedi obe polovice a spojí ich zlučovaním dvoch utriedených postupností.
• - Triviálny prípad rekurzie v Merge Sorte je úsek s jedným alebo žiadnym prvkom, kde sa nič nerobí.

Zhrnutie pripravené s pomocou AI z prepisu videa.