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("n"log "n").
Lajittelualgoritmeja on kehitetty paljon, yleisimmät algoritmit ovat: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.
Lajittelualgoritmit voidaan luokitella sen mukaan, toimiiko lajittelualgoritmi "paikallaan" ja onko se "vakaa":
Epävakaita lajittelualgoritmeja ovat mm:Vakaita lajittelualgoritmeja ovat mm:Minimitilassa toimivat muun muassa:Esimerkki: Pöydällä on neljä korttipakan korttia, jotka haluamme järjestää sekä aakkos- että numerojärjestykseen:
Käytämme "Epävakaata" lajittelualgoritmia järjestämään listan aakkosjärjestykseen:
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:
Kortit ovat nyt numerojärjestyksessä ja jokainen numero on omalta kohdaltaan myös aakkosjärjestyksessä.
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ä:
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)".