Skaitmeninis rikiavimo algoritmas

Skaitmeninis rikiavimas () – vienas iš rikiavimo algoritmų, skirtas atvejams, kai duomenų reikšmės yra skaitmeninės ir priklauso kokiam nors skaitiniam intervalui ar išsiskiria panašiomis savybėmis. Skaitmeninio rikiavimo algoritmuose duomenų reikšmės interpretuojamos kaip skaičiai M-tainėje (dažniausiai – dvejetainėje) skaičiavimo sistemoje. Algoritmas stabilus ir labai greitas, sudėtingumas – O(N·k) (k – rakto ilgis). Pirmasis skaitmeninio rikiavimo algoritmas kompiuteriui parašytas 1954 metais.

Dažniausiai naudojamos skaitmeninio rikiavimo procedūros: skaitmeninio keitimo
(radix exchange sort) ir tiesioginio skaitmeninio rikiavimo (straight radix sort). Skaitmeninio keitimo metodas naudoja apie N·logN bitų lyginimų. Abu skaitmeniniai metodai, rikiuodami N skaičių, kurių kiekvienas yra b bitų ilgio, naudoja mažiau negu N·b bitų lyginimų.

Skaitmeninis rikiavimo algoritmas jau buvo naudojamas 1887 m., kai amerikietis Hermanas Holeritas (Herman Hollerith) dirbo su tabuliatoriumi. ir 

 Šaltiniai 

Kategorija:Rikiavimo algoritmai

no:Sorteringsalgoritme#Radix-sortering