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).

Yleisimpiä lajittelualgoritmeja

Lajittelualgoritmeja on kehitetty paljon, yleisimmät algoritmit ovat:

Kantalukulajittelu (Radix sort)
Kekolajittelu (Heap sort)
Kuplalajittelu (Bubble sort)
Laskentalajittelu (Counting sort)
Lisäyslajittelu (Insertion sort)
Lomituslajittelu (Merge sort)
Nippulajittelu (Bucket sort)
Pikalajittelu (Quicksort)
Shell-lajittelu (Shell sort)
Vaihtolajittelu (Exchange sort)
Valintalajittelu (Selection sort)
Helmilajittelu (teoreettinen) (Bead sort)

Sopivan algoritmin valinta riippuu käytettävän tietojoukon koosta, tietojoukon sisällön arvojakaumasta, käytössä olevan muistin määrästä ja tavoitteena olevasta suoritustehosta. Lopputuloksen kannalta oleellista on tietää halutaanko lajittelualgoritmin olevan vakaa vai riittääkö epävakaa -algoritmi.

Lajittelualgoritmien luokittelu

Lajittelualgoritmit voidaan luokitella sen mukaan, toimiiko lajittelualgoritmi paikallaan ja onko se vakaa:

Vakaa (stabiili) lajittelualgoritmi ei vaihda keskenään samansuuruisen alkion suhteellista järjestystä, kun taas epävakaa saattaa niin tehdä.
Paikallaan toimiva (minimitila) lajittelualgoritmi ei tarvitse toimiakseen kuin kiinteän määrän lisää muistitilaa lajiteltavalle tietorakenteelle, eli sen tilavaatimus on O(1). Tämä on tärkeää jos muistitila on rajattu.

Epävakaita lajittelualgoritmeja ovat mm:

Pikalajittelu
Kekolajittelu
Valintalajittelu
Shell-lajittelu

Vakaita lajittelualgoritmeja ovat mm:

Lomituslajittelu
Laskentalajittelu
Lisäyslajittelu
Kuplalajittelu

Minimitilassa toimivat muun muassa:

Lisäyslajittelu
Kekolajittelu
Shell-lajittelu

Esimerkki: Pöydällä on neljä korttipakan korttia, jotka haluamme järjestää sekä aakkos- että numerojärjestykseen:

ruutu 9, pata 10, hertta 9, hertta 11

Käytämme Epävakaata lajittelualgoritmia järjestämään listan aakkosjärjestykseen:

hertta 11, hertta 9, pata 10, ruutu 9

Huomataan, että kortit ovat kyllä aakkosjärjestyksessä, mutta hertta 9 ja hertta 11 ovat vaihtaneet paikkaa verrattuna alkuperäiseen järjestykseen. Haluamme nyt säilyttää aakkosjärjestyksen, joten käytämme vakaata lajittelualgoritmia muuttamaan listan numerojärjestykseen. Vakaa-algoritmi palauttaisi listan:

hertta 9, ruutu 9, pata 10, hertta 11

Kortit ovat nyt numerojärjestyksessä ja jokainen numero on omalta kohdaltaan myös aakkosjärjestyksessä.

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).