Kantalukulajittelu

Wikipedia

Kantalukulajittelu (Radix sort) on eräs lajittelualgoritmeista. Se perustuu numeroiden merkitsevyyden perusteella tehtävään lajitteluun. Se on vakaa (ei sotke alkioiden alkuperäistä järjestystä). Lajittelu aloitetaan vähiten merkitsevästä arvosta. Itse kantaluvun pohjalta tehty lajittelu käyttää apuna laskentalajittelua.

RADIX-SORT(A, d)
for int i = 0 to d
{
 // Lajittele alkiot laskentalajittelun avulla stabiilisti paikan i suhteen
}

n = lajiteltavien lukujen määrä k = kantaluku (10-järjestelmässä 10, aakkostossa esim. 24 jne...)

Kompleksisuus on yhteensä O(d(n+k))

n+k tulee counting-sortista, ja sitä suoritetaan d kertaa.

[muokkaa] Esimerkki

Esimerkki kantalukulajittelusta 10-järjestelmän luvuilla:

Lajiteltavat:
423
253
126
873
112

Ensin lajitellaan vähiten merkitsevän (ykkösten) mukaan, counting-sortilla. Tulos on:
412
123
253
873
126

Sitten kymmenten mukaan:
412
123
126
253
873

Ja lopuksi satojen mukaan:
123
126
253
412
873

Tuloksena luvut on lajiteltu stabiilisti suuruusjärjestykseen. 

Tätä voidaan hyödyntää esimerkiksi nimiä lajittelemalla, jolloin sukunimen mukaan tehty lajittelu säilyy etunimen mukaan tehdyn lajittelun aikana.