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.