ADŠ prednáška 11: CountSort, RadixSort, BucketSort.

Zhrnutie prednášky

Prednáška nadväzuje na dolný odhad n log n pre triedenie porovnávaním a ukazuje, že ho možno obísť, ak o triedených dátach vieme niečo navyše, napríklad že kľúče sú malé prirodzené čísla z rozsahu 0 až k−1. Úvodná poznámka vysvetľuje, že pôvodný význam slova triedenie je rozdeľovanie do tried, kým správny pojem pre zoraďovanie je usporadúvanie. Hlavnou témou je CountSort: najprv sa spočítajú výskyty kľúčov do poľa počtov, z nich sa prefixovými súčtami určia začiatočné pozície úsekov jednotlivých kľúčov vo výstupnom poli a následne sa celé prvky presúvajú na tieto pozície. Vysvetľuje sa tiež, prečo nestačí iba vygenerovať usporiadané kľúče, keďže treba usporiadať celé objekty.

• - Dolný odhad n log n platí len pre triedenie založené výlučne na porovnávaní prvkov.
• - Pri znalosti dodatočných vlastností dát (malý rozsah kľúčov) sa dá usporiadať v lineárnom čase.
• - Slovo triedenie pôvodne znamenalo rozdeľovanie do tried; správny pojem je usporadúvanie.
• - CountSort najprv spočíta výskyty každého kľúča do poľa počtov P veľkosti k.
• - Prefixové súčty poľa P určujú, na ktorej pozícii vo výstupnom poli začína úsek prvkov s daným kľúčom.
• - Nestačí vyplniť výstup samotnými kľúčmi, treba umiestniť celé objekty podľa ich kľúčov.
• - Výstupné pole B má dĺžku N a prvky sa doň umiestňujú prechodom cez vstupné pole pomocou prefixových súčtov.

Zhrnutie pripravené s pomocou AI z prepisu videa.