Cvicenie - Vypoctova zlozitost algoritmov 4.11.2020 13:30

Zhrnutie prednášky

Cvičenie prechádza riešenia testu zameraného na bublinové triedenie osemprvkovej postupnosti celých čísel. Počet porovnaní vychádza 28, pretože for cykly majú pevný počet opakovaní a ten závisí len od počtu prvkov n, nie od ich hodnôt; všeobecne ide o súčet n(n−1)/2. Počet výmen naopak závisí od hodnôt a rovná sa počtu inverzií v poli, ktorý je tu 17. Inverzie sa počítajú buď ako menšie čísla za daným prvkom, alebo ako väčšie čísla pred ním, a pri zmene smeru triedenia sa ich definícia obráti. Na záver cvičenie začína tretiu úlohu porovnávajúcu počet výmen v bubble sorte a shaker sorte, kde sa smer prechodu strieda.

• - Bublinové triedenie porovnáva susedné prvky a pri väčšom prvku pred menším ich vymení, takže usporadúva vzostupne.
• - Počet porovnaní je n(n−1)/2, pre n = 8 teda 28, a nezávisí od hodnôt prvkov, pretože for cykly majú pevný počet opakovaní.
• - Počet výmen závisí od hodnôt čísel a rovná sa počtu inverzií v poli, lebo každá výmena odstráni práve jednu inverziu.
• - Inverzia pri vzostupnom triedení je menší prvok za daným číslom alebo väčší prvok pred ním; pre zadanú postupnosť je ich 17.
• - Pri triedení opačným smerom sa význam inverzie obráti, preto je treba vždy určiť, ktoré poradie dvojice je nesprávne.
• - Shaker sort je bublinové triedenie so striedavým smerom prechodu: raz sa minimum posúva dopredu, raz maximum dozadu.

Zhrnutie pripravené s pomocou AI z prepisu videa.