Lajittelualgoritmi

Wikipedia

Lajittelualgoritmit eli järjestämisalgoritmit ovat varsin keskeisiä algoritmeja ohjelmistotekniikassa. Niitä on useita erilaisia eri käyttötarkoituksia varten.

• 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)
• Valintalajittelu (Selection sort)
• Helmilajittelu (teoreettinen) (Bead sort)

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.

[muokkaa] 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 esim. 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).

1. Kertaluokkamerkintä O(n) selitetään artikkelissa asymptoottinen suoritusaika.