Kantalukulajittelu

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

 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 

Luokka:Lajittelualgoritmit

no:Sorteringsalgoritme#Radix-sortering