Pikalajittelu ja lomituslajittelu

Abstract

Järjestysalgoritmit ovat hyvin yleisiä algoritmeja ohjelmissa. Sen vuoksi on tärkeää, että ohjelmaan on valittu oikea algoritmi ja että se on toteutettu mahdollisimman tehokkaasti. Jos käyttötapaukseen on valittu epäsopiva algoritmi, ohjelman tehokkuus voi heikentyä huomattavasti.

Hajota ja hallitse -suunnitteluperiaatteen mukainen algoritmi jakaa alkuperäisen ongelman pienempiin osaongelmiin, jotka voidaan ratkaista itsenäisesti. Kun osaongelmat on ratkaistu, voidaan ne yhdistää takaisin yhteen. Näin saadaan alkuperäisen ongelman ratkaisu. Pikalajittelu ja lomituslajittelu ovat hajota ja hallitse -suunnitteluperiaatteen mukaisia järjestysalgoritmeja. Näiden algoritmien toteutuksissa on kuitenkin eroavaisuuksia, minkä vuoksi niiden soveltuvuus eri käyttötapauksiin vaihtelee.

Tämän työn tarkoituksena on selvittää pikalajittelun ja lomituslajittelun soveltuvuus eri käyttötapauksiin. Tässä käytetään apuna niin aiempia tutkimuksia kuin itse suoritettuja suoritusaikatestejä. Tutkimusta varten suoritusaikatestit toteutettiin lomituslajittelulle, single-pivot-pikalajittelun kolmelle erilaiselle toteutukselle ja yhdelle dual-pivot-pikalajittelun toteutukselle. Suoritusaikatesteissä käytettiin sekä satunnaisessa järjestyksessä olevaa dataa että järjestyksessä olevaa dataa.

Suoritusaikatesteistä voidaan havaita, että mikäli ohjelma käsittelee usein järjestyksessä olevaa dataa tai melkein järjestyksessä olevaa dataa, perinteinen pikalajittelu ei ole hyvä vaihtoehto taulukon järjestämiseksi. Jos tiedetään, että ohjelma käsittelee satunnaisesti melkein järjestyksessä olevaa dataa, on kokonaistehokkuuden kannalta järkevintä käyttää lomituslajittelua, koska sillä ei ole yhtä tehotonta huonointa tapausta kuin pikalajittelulla.

Aiempien tutkimuksien perusteella sopivan järjestysalgoritmin valitsemisessa kannattaa huomioida myös muut asiat kuin pelkkä tehokkuus. Jos ohjelma käsittelee hyvin suuria tietojoukkoja, jotka eivät mahdu kerrallaan prosessoivan tietokoneen muistiin, kannattaa käyttää lomituslajittelun ulkoista järjestelyä. Tällä tavoin järjestettävää tietojoukkoa ei tarvitse lukea kokonaisuudessaan prosessoivan tietokoneen muistiin. Lomituslajittelu on valittava myös, jos ohjelma tarvitsee stabiilin järjestysalgoritmin, koska pikalajittelu ei ole stabiili järjestysalgoritmi.