Järjestysalgoritmien tehokkuuden vertailu : pika-, lomitus- ja kuplalajittelun erot

Abstract

Järjestysalgoritmien merkitys yhteiskunnalle on kasvanut viime vuosina datan määrän räjähdysmäisen kasvun takia. Datan käsittely vaatii usein datan järjestämistä, sillä monet algoritmit vaativat syötteeksi ottamansa datan olevan tietyssä järjestyksessä. Näin ollen järjestysalgoritmin suoritusaika voi vaikuttaa paljon itse algoritmia suurempien kokonaisuuksien suoritustehoon. Järjestysalgoritmeja on kuitenkin monia, ja niiden tehokkuuksissa voi olla suuria eroja. Tämän takia oikean järjestysalgoritmin valinta ei aina ole helppoa. Tämän työn tarkoitus on helpottaa valintaa työssä käsiteltävien algoritmien osalta. Työssä vertaillaan kolmea järjestysalgoritmia, keskittyen erityisesti niiden tehokkuuteen ja tehokkuuksien eroihin. Algoritmit ovat pikalajittelu (engl. quicksort), lomituslajittelu (merge sort) ja kuplalajittelu (bubble sort). Vertailu on toteutettu osittain kirjallisuuskatsauksena ja osittain empiirisenä tutkimuksena. Kirjallisuuskatsauksessa käsitellään aiempien, kyseisiä algoritmeja vertailevien tutkimusten tuloksia. Omassa tutkimuksessa mitattiin algoritmien tehokkuuksia eri kokoisilla standardoiduilla datajoukoilla. Joukot koostuivat satunnaisesta positiivisesta datasta, satunnaisesta negatiivisesta datasta, järjestetystä ja käänteisesti järjestetystä datasta sekä lähes järjestetystä datasta. Tutkielman perusteella kuplalajittelu on keskimääräisessä tapauksessa huomattavasti hitaampi kuin pikalajittelu tai lomituslajittelu. Pika- ja lomituslajittelun välinen ero ei ollut yhtä selvä. Lomituslajittelu oli suurimmassa osassa tutkimuksia nopeampi kuin pikalajittelu. Kuitenkin osassa tutkimuksista järjestys oli päinvastainen. Pikalajittelun suurin heikkous on sen tehokkuus huonoimmassa mahdollisessa tilanteessa. Tällöin sen tehokkuus on jopa kuplalajittelua huonompi. Lomituslajittelun tehokkuus taas pysyi lähes vakiona datan muodosta riippumatta. Näin ollen lomituslajittelua voidaan pitää yleisesti parhaana tutkielmassa käsitellyistä algoritmeista.