Kantalukulajittelu

Tietojenkäsittelytieteessä kantalukulajittelu (kantalukujärjestäminen, reikäkorttijärjestäminen, engl. radix sort) 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

• Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: Introduction to Algorithms – 2nd ed. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7.