Radixové triedenie - MSD

Zhrnutie prednášky

Prednáška sa venuje radixovému triedeniu reťazcov rovnakej dĺžky v dvoch variantoch, LSD (od posledného znaku) a MSD (od prvého znaku), s cieľom získať lexikografické usporiadanie ako v slovníku. Na príklade piatich reťazcov nad abecedou A, B, C, D s dĺžkou tri znaky lektor upravuje existujúcu implementáciu radu z typu int na reťazce (využíva strcpy pri kopírovaní hodnôt). Algoritmus používa pole štyroch radov, po jeden pre každé písmeno, pričom index sa získa odpočítaním znaku 'A'. V každom kroku sa reťazce rozdelia do radov podľa znaku na danej pozícii a potom sa v poradí radov 0 až 3 vyberú späť do pôvodného radu. Pri prvom spustení výstup nebol správne zoradený, preto lektor začína postup opakovane vysvetľovať.

• - Radixové triedenie má dva varianty: LSD (od konca reťazca) a MSD (od začiatku).
• - Cieľom je lexikografické usporiadanie reťazcov rovnakej dĺžky nad abecedou A, B, C, D.
• - Rad sa upraví z ukladania int na ukladanie reťazcov a hodnoty sa kopírujú pomocou strcpy.
• - Používa sa pole štyroch radov, po jednom pre každé písmeno abecedy.
• - Index radu sa vypočíta odčítaním 'A' od znaku (A→0, B→1, C→2, D→3).
• - V každom kroku sa reťazce rozdelia do radov podľa znaku na danej pozícii a potom sa vyberú späť v poradí radov 0 až 3.
• - Pri prvom spustení bol výsledok nesprávne zoradený, čo viedlo k opakovanému vysvetľovaniu postupu.

Zhrnutie pripravené s pomocou AI z prepisu videa.