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 ${\displaystyle O(n)}$. Se on stabiili, mutta ei toimi minimitilassa. Algoritmin kompleksisuudesta käytetään yleisesti myös muotoa ${\displaystyle O(n+k)}$, missä ${\displaystyle n}$ tarkoittaa järjesteltävien alkioiden määrää ja ${\displaystyle k}$ alkioiden mahdollisten arvojen lukumäärää. Usein ${\displaystyle 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 ${\displaystyle k}$ on tarpeeksi pieni. Tarkemmin sanottuna, kun ${\displaystyle 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".