Tietojenkäsittelytieteessä kantalukulajittelu (kantalukujärjestäminen, reikäkorttijärjestäminen, ) on lajittelualgoritmi, joka lajittelee lukuja suuruusjärjestykseen numeroiden merkitsevyyden perusteella. Siten se ei ole yleiskäyttöinen vertailuun pohjautuva lajittelualgoritmi, mutta käyttäen apuna laskentalajittelua se suoriutuu lineaarisessa ajassa. Myös kirjaimia voidaan ajatella numeroina, jolloin voidaan lajitella merkkijonoja. Kantalukulajittelu on vakaa eli se ei sotke alkioiden alkuperäistä järjestystä.
Kantalukulajittelu keksittiin jo ennen tietokoneiden aikakautta, mutta 1950-luvulla Harold H. Seward keksi tietokoneille tarkoitetun kantalukulajittelun.
Algoritmi Lajitellaan luvut vähiten merkitsevän numeron perusteella jollakin vakaalla lajittelualgoritmilla. Lajitellaan luvut toiseksi vähiten merkitsevän numeron perusteella... Kun kaikki numerot on käyty läpi, luvut ovat järjestyksessä.
A: taulukko, jonka alkiot ovat lukuja d: luvussa olevien numeroiden lukumäärä
procedure radix_sort(A, d) for i := 1 to d do lajittele alkiot i:nneksi vähiten merkitsevän numeron suhteen laskentalajittelun avulla (jokin toinen vakaa lajittelualgoritmi toimii myös) end for end procedure
Suorituskyky Kantalukulajittelun asymptoottinen aikavaativuus on O(d · (n + k)), missä d on numeroiden lukumäärä luvuissa, n on lajiteltavien lukujen lukumäärä, k on kantaluku (10-lukujärjestelmässä 10, länsimaisissa aakkosissa vähintään 26 jne.), käytetään laskentalajittelua O(n + k).
Aikavaativuus voidaan johtaa yksinkertaisesti siitä, että laskentalajittelua toistetaan d kertaa.
Kantalukulajittelu ei ole yksiselitteisesti parempi kuin yleiset, ajassa O(n log n) suoriutuvat algoritmit. Apuna käytetty laskentalajittelu vie muistia kantaluvun koosta riippuen, siinä missä pikalajittelu toimii vakiotilassa ja käyttää välimuistia tehokkaasti hyväkseen.
Esimerkki Lajiteltavat: 423 253 126 873 112 Ensin lajitellaan vähiten merkitsevien numeroiden (ykkösten) mukaan. Tulos on: 112 423 253 873 126 Seuraavaksi lajitellaan kymmenten mukaan. Järjestys säilyy oikeana, koska käytetään vakaata lajittelualgoritmia: 112 423 126 253 873 Lopuksi lajitellaan satojen mukaan: 112 126 253 423 873 Tuloksena luvut on lajiteltu vakaasti suuruusjärjestykseen.
Kantalukulajittelu yleisenä periaatteena
Kantalukulajittelua voidaan ajatella yleisenä periaatteena, jossa vähiten merkitsevä tieto lajitellaan ensin. Päivämäärät voidaan lajitella ensin päivien, sitten kuukausien ja lopuksi vuosien mukaan. Nimet voidaan lajitella ensin etunimen mukaan ja lopuksi sukunimen mukaan. Jokainen kantalukulajittelun periaatteella toimiva lajittelu vaatii ehdottomasti vakaan lajittelualgoritmin ja on hyvä esimerkki vakauden avulla saavutettavasta hyödystä.
Katso myös Asymptoottinen aikavaativuus Kantaluku Lajittelualgoritmi Laskentalajittelu Lomituslajittelu Pikalajittelu
Lähteet
Viitteet
Luokka:Lajittelualgoritmit
no:Sorteringsalgoritme#Radix-sortering