Skaitmeninis rikiavimo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
Algoritmas
Tipas Rikiavimo algoritmai
Pavadinimas Skaitmeninis (Radix sort)
Sudėtingumas Vidutinis - N; blogiausias - N
Greitos nuorodos

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ų.