Laskentalajittelu

Laskentalajittelu (Counting sort) on eräs lajittelualgoritmeista. Se perustuu jakauman laskemiseen. Ajatuksena on, että aineiston järjestäminen voidaan suorittaa tehokkaasti, jos alkioiden keskinäistä vertailua ei tarvitse tehdä aina kokonaisilla alkioilla.

Algoritmin aikakompleksisuus on lineaarinen eli $O(n)$. Se on stabiili, mutta ei toimi minimitilassa. Algoritmin kompleksisuudesta käytetään yleisesti myös muotoa $O(n+k)$, missä $n$ tarkoittaa järjesteltävien alkioiden määrää ja $k$ alkioiden mahdollisten arvojen lukumäärää. Usein $k$ lasketaan dynaamisesti alkioiden maksimi ja minimiarvojen erotuksena avulla.

Koska n-suuruisen syötteen järjestäminen kokonaisia alkioita vertaamalla vaatii pahimmassa tapauksessa Ω(n log n) vertailua, on laskentalajittelu varsin tehokas menetelmä, kunhan oletettu $k$ on tarpeeksi pieni. Tarkemmin sanottuna, kun $k<n(log(n)-1)$.

Laskentalajittelu tarvitsee väliaikaistaulukkoa. Näin ollen laskentalajittelu ei ole minimitila-algoritmi (vaatii ylimääräistä tilaa).

Laskentalajittelun periaate on seuraava:

1. Luodaan apuvektori, jonka ensimmäisen alkion indeksi on lajiteltavan syötteen pienin arvo (tai pienempi) ja viimeisen alkion indeksi lajiteltavan syötteen suurin arvo (tai suurempi). Esimerkiksi, jos lajiteltavana on lukuja väliltä 0..5, apuvektorin koko on 6.
2. Lasketaan jokaisen syötevektorin sisältämän numeron esiintymien lukumäärät (jakauma) yhteen, ja´tallennetaan tulos apuvektoriin kyseisen luvun kohdalle.
3. Lasketaan kumulatiivinen jakauma samaan apuvektoriin siten, että jokainen arvo sisältää edellä olleiden arvojen ja oman arvonsa summan.
4. Luodaan tulosvektori, jonka koko on sama kuin syötevektorin.
5. Käydään läpi syötevektori lopusta alkuun päin, ja sijoitetaan syötevektorin arvo tulosvektoriin sille paikalle, jonka apuvektori ilmoittaa kyseiselle arvolle. Tämän jälkeen apuvektorin ko. paikan arvoa vähennetään yhdellä.

Edellä oleva periaate soveltuu tapauksiin, joissa avainavaruus on pienempi kuin lajiteltavien alkioiden määrä. Ts. menetelmästä tulee käyttökelvoton, jos mahdollisia avaimia on enemmän kuin lajiteltavia avaimia, koska apuvektorin koko kasvaa valtavaksi. Tästä syystä yleisessä tapauksessa em. menetelmää sovelletaan järjestämällä aineisto samalla periaatteella useampaan kertaan eri avaimen osien suhteen: ensin vähiten merkitsevien avaimen osien suhteen edeten kohti eniten merkitseviä avaimen osia. Koska menetelmä on stabiili, säilyttävät vähiten merkitsevien osien mukaan järjestetyt osat järjestyksensä. Näin aineisto voidaan järjestää "paloittain".

Esimerkki

Esimerkki laskentalajittelusta:

Olkoon A 10:n pituinen syötevektori  // A[1..10]
A = {5,0,1,4,4,5,0,4,1,3} // A:n sisältö

Havaitaan, että vektorin A pienin arvo on 0 ja suurin 5. Periaatteen mukaisesti kohta 1. on nyt tehty. Näin ollen muodostetaan apuvektori B:

Olkoon B 6:n pituinen apuvektori // B[0..5]

Apuvektori B:n sisällöksi sijoitetaan numeroiden esiintymien lukumäärät:

B = {2,2,0,1,3,2}

Nollia siis 2, ykkösiä 2, kakkosia 0, kolmosia 1, nelosia 3 ja vitosia 2. Periaatteen kohta 2. on nyt tehty. Seuraavaksi kohta 3, eli lukujen kumulointi:

B = {2,4,4,5,8,10}

Eli:

 
1. alkio -> 2
1. alkio + 2. alkio -> 4
1. alkio + 2. alkio + 3. alkio -> 4
1. alkio + 2. alkio + 3. alkio + 4. alkio -> 5
1. alkio + 2. alkio + 3. alkio + 4. alkio + 5. alkio -> 8
1. alkio + 2. alkio + 3. alkio + 4. alkio + 5. alkio + 6. alkio -> 10

Nyt kohta 3. on tehty. Havaitaan myös, että B:n viimeisen alkion kumuloitunut arvo (10) on sama kuin syötevektorin A viimeinen indeksi. Seuraavaksi kohta 4.

Olkoon C 10:n pituinen tulosvektori // C[1..10]

Kohta 4. tehty, siirrytään kohtaan 5.

Aluksi C = { , , , , , , , , , , }
Lähdetään käymään vektoria A läpi lopusta alkuun päin. 
Viimeinen luku A:ssa on 3. 
Katsotaan apuvektorista B sen sijainti tulosvektorissa C. 
Kolmonen menee siis paikalle 5. (Koska B[3] = 5). 
C = { , , , ,3, , , , , }
Vähennetään B[3]:n arvoa yhdellä.
Toiseksi viimeinen luku A:ssa on 1. Sen paikka on 4. (Koska B[1] = 4)
C = { , , ,1,3, , , , , }
Vähennetään B[1]:n arvoa yhdellä.
Jatketaan taaksepäin: luku 4, sen paikka on 8. (Koska B[4] = 8)
C = { , , ,1,3, , ,4, , }
Vähennetään B[4]:n arvoa yhdellä.
Luku 0, sen paikka on 2.
C = { ,0, ,1,3, , ,4, , }
Vähennetään B[0]:n arvoa yhdellä.
Luku 5, sen paikka on 10.
C = { ,0, ,1,3, , ,4, ,5}
Vähennetään B[5]:n arvoa yhdellä.
Luku 4, sen paikka on nyt 7. 
C = { ,0, ,1,3, ,4,4, ,5}
Vähennetään B[4]:n arvoa yhdellä.
Luku 4, sen paikka on nyt 6. 
C = { ,0, ,1,3,4,4,4, ,5}
Vähennetään B[4]:n arvoa yhdellä.
Luku 1, sen paikka on nyt 3. 
C = { ,0,1,1,3,4,4,4, ,5}
Vähennetään B[1]:n arvoa yhdellä.
Luku 0, sen paikka on nyt 1. 
C = {0,0,1,1,3,4,4,4, ,5}
Vähennetään B[0]:n arvoa yhdellä.
Viimeinen käsiteltävä luku on 5, sen paikka on nyt 9.
C = {0,0,1,1,3,4,4,4,5,5}
Vähennetään B[5]:n arvoa yhdellä.

Näin koko syötevektori käytiin läpi ja tulosvektori sisältää samat arvot kuin syötevektori, stabiilisti lajiteltuna.

Aiheesta muualla

• Esimerkkitoteutukset Haskell- ja Python-kielillä. (Arkistoitu – Internet Archive)