Algoritmy triedenia - SelectSort, InsertSort, BubbleSort, ShellSort

Zhrnutie prednášky

Prednáška úvodom motivuje triedenie jednorozmerných polí príkladmi z bežného života, ako je radenie hracích kariet alebo zoraďovanie žiakov podľa výšky. Prednášajúci vysvetľuje, že tento semester sa preberú jednoduché algoritmy založené na cykloch (SelectSort, BubbleSort, InsertSort, ShellSort) s kvadratickou časovou zložitosťou O(n²), kým v ďalšom roku budú nasledovať algoritmy typu rozdeľuj a panuj (HeapSort, QuickSort, MergeSort) a radixové triedenie. Časová zložitosť sa podrobne preberie nabudúce a správnosť algoritmov sa bude dokazovať pseudoindukciou, pričom insert sort poslúži ako vzorový príklad. Na ukážku činnosti SelectSortu slúži video s maďarskými tanečníkmi, kde sa opakovane hľadá najmenší prvok a zaraďuje sa na začiatok poľa, čím vzniká invariantná usporiadaná časť.

• - Triedenie (usporiadanie) poľa je popri vyhľadávaní základnou oblasťou algoritmov.
• - SelectSort opakovane vyberie najmenší prvok z nezoradenej časti a zaradí ho na začiatok.
• - Invariant je už zotriedená časť poľa, ktorá sa ďalej nemení.
• - Jednoduché triedenia (Select, Bubble, Insert, Shell) majú kvadratickú zložitosť O(n²).
• - Pokročilé algoritmy (HeapSort, QuickSort, MergeSort) typu rozdeľuj a panuj majú zložitosť O(n log n); QuickSort je v C dostupný ako qsort.
• - Správnosť algoritmov sa bude dokazovať pseudoindukciou a zložitosť sa odhadne na InsertSorte a MergeSorte.
• - Záznamy sa budú triediť podľa kľúča, nielen jednoduché číselné polia.

Zhrnutie pripravené s pomocou AI z prepisu videa.