Lajittelualgoritmi

Lajittelualgoritmit eli järjestämisalgoritmit ovat varsin keskeisiä algoritmeja ohjelmistotekniikassa. Lajittelualgoritmin tarkoitus on järjestää lista sovittuun järjestykseen, esimerkiksi numero- tai aakkosjärjestykseen. Lajittelualgoritmeilla on keskeinen merkitys sovelluksissa, jotka käsittelevät suuria tietomääriä. Lajittelualgoritmien nopeutta on tutkittu ohjelmistotekniikassa verrattain paljon niiden merkittävyyden vuoksi. Parhaiden yleiskäyttöisten lajittelualgoritmien asymptoottinen suoritusaika on luokkaa O(nlog n).

Suoritusajoista

Yleisesti voidaan todeta, että luokkaa O(n²) olevat algoritmit ovat liian tehottomia käytettäväksi. Logaritmifunktio taas kasvaa niin hitaasti, että O(n log n) luokkaa olevat algoritmit ovat jo kelvollisia - näissä termin log n painoarvo siis vähenee syötteen kasvaessa. O(n) luokkaa olevat algoritmit toimivat erittäin nopeasti, mutta vaativat vastaavasti usein lisätilaa/lisäinformaatiota järjestämiseen.
Lajittelualgoritmin oikea valinta on erittäin tärkeää. Mikäli tiedetään ennalta syötteen kasvavan suureksi, ei käytetä hitaita algoritmeja. Vastaavasti, jos tiedetään syötteen jäävän useimmissa tapauksissa pieneksi, voidaan käyttää hitaampia (yksinkertaisempia) toteutuksia: hajautustaulujen alkioiden ketjutuksessa esiintyvän linkitetyn listan järjestäminen tehdään usein lisäyslajittelulla, sillä alkioiden määrä jää usein pieneksi. Esimerkki algoritmin valinnan merkityksestä:

Oletetaan:
- Suoritin A suorittaa 1 000 000 alkeisoperaatiota sekunnissa.
- Suoritin B suorittaa 1 000 000 000 alkeisoperaatiota sekunnissa.
- Algoritmien suoritusvakiokerroin on 40 (korkean tason ohjelmointikieli)

Reaali suoritusaika eri kokoisilla lukusyötteillä väliltä 0..9
suhteessa käytettyyn algoritmiin:

Algoritmi Syötteen koko Operaatioita Käytetty aika
-----------------------------------------------------------------------------
Lisäyslajittelu B:llä 1 000 000 40 000 000 000 000 ~11h 6min 20sec
Laskentalajittelu A:lla 10 000 000 400 000 400 ~6min 21sec

Siis: huolimatta siitä, että B on 1000 kertaa nopeampi suoritin ja 
B:n saama syöte on 10 kertaa pienempi, aikaa lajitteluun tuhrautui 11 tuntia kauemmin,
kuin jos valittaisiin laskentalajittelu. 
Voidaan todistaa, että suuruusarvojen vertailuun perustuvan lajittelualgoritmin asymptoottinen suoritusaika on aina vähintään kertaluokkaa O(n log n), jossa n on lajiteltavien alkioiden lukumäärä. (Kuitenkaan esimerkiksi Counting sort ei toimi vertailulla.)
Esimerkiksi lomituslajittelu on vakaa, mutta ei toimi paikallaan vaan vaatii alkioille O(n) lisämuistia. Sen suoritusnopeus on kuitenkin aina O(n lg n). Sen sijaan Insertion sort on vakaa ja toimii paikallaan, mutta sen suoritusnopeus on pahimmillaan kertaluokkaa O(n²).
Yleinen pikalajittelu vaatii keskimäärin O(n log(n)) vertailua, mutta pahimmassa tapauksessa O(n²), jos järjestettävät alkiot ovat jo valmiiksi järjestyksessä. Pikalajittelu on kevyt ja nopea lähes kaikilla suorittimilla, joka tekee siitä nopeamman kuin muut O(n log(n))-algoritmit. Pikalajittelun tilavaatimus on O(log n) keskimäärin ja O(n) pahimmassa tapauksessa. Pikalajittelun pahimman tilanteen välttämiseksi voidaan siihen liittää algoritmi, joka ennen järjestämistä sekoittaa järjestettävät alkiot epäjärjestykseen.
Laskentalajittelu toimii hyvin nopeasti, O(n) ajassa, mutta vaatii tilapäisvektorin tallennustilaksi käsiteltävän lukuavaruuden suurimman ja pienimmän arvon erotuksen verran lisämuistia. Kantalukulajittelu hyödyntää laskentalajittelua - tällöin riittää tietää tietotyypin minimi ja maksimi, ja tämän jälkeen käsitellä kokonainen syöte käyttäen kantalukua. (Esimerkiksi tekstirivit saadaan aakkosjärjestykseen kantalukulajittelulla, kun sen käyttämän laskentalajittelun apuvektorin kooksi asetetaan aakkoset, esimerkiksi a-z.) Näin laskentalajittelun lisämuistitarve saadaan vähennettyä siedettäväksi samalla kun lajittelun suoritusaika pysyy luokassa O(n).