Lajittelualgoritmin valitseminen eri tilanteissa

Abstract

Lajittelualgoritmeja käytetään esimerkiksi hakukoneiden tulosten, kauppojen tuotteiden ja musiikkipalvelujen kappaleiden esittämisessä, joten lajittelualgoritmitien nopeus on usein suoraan verrannollinen koko ohjelmiston nopeuteen. Tässä työssä tutkitaan eri lajittelualgoritmien ominaisuuksia, hyötyjä ja haittoja relevantin kirjallisuuden ja empiiristen tutkimusten avulla. Tämän kautta yritetään selvittää, että mitkä lajittelualgoritmit ovat tehokkaimpia mihinkin tilanteisiin. Tehokkaimman lajittelualgoritmin valitsemiseen vaikuttaa esimerkiksi alkioiden määrä, saatavilla olevan muistin määrä, alkioiden suhteellisen järjestyksen ylläpitäminen, alkioiden alkuperäinen järjestys, alkioiden jakauma ja samanarvoisten alkioiden yleisyys. Työssä keskitytään yksiulotteisen taulukon alkioiden lajittelemiseen.

Työssä käydään läpi 11 lajittelualgoritmia, joiden valikoitumiseen vaikutti algoritmien hyvä tehokkuus eri tilanteissa ja niiden toistuvuus relevantissa kirjallisuudessa. Valitut lajittelualgoritmit ovat: insertion sort, merge sort, heap sort, quicksort, selection sort, shellsort, introsort, timsort, bucket sort, counting sort ja radix sort. Näistä kolme viimeistä, eli bucket sort, counting sort ja radix sort ovat vertailuun perustumattomia lajittelualgoritmeja, jotka nimensä mukaan eivät käytä alkioiden lajittelemiseen suoraa alkioiden arvojen vertailua. Työssä tutkitaan lajittelualgoritmien aika- ja tilavaativuuksia, vakautta ja suosituimpia optimointeja.

Tutkimuksista saatiin paljon tuloksia. Jokaiselle valitulle lajittelualgoritmille löytyi tilanne, jossa kyseinen algoritmi on optimaalisin valinta. Insertion sort osoittautui nopeimmaksi pienikokoisilla, alle 16 alkion pituisilla taulukoilla. Introsort on yleiskäyttöisin ja nopein epävakaa lajittelualgoritmi, soveltuen hyvin suurten alkiomäärien lajitteluun ja lajittelualgoritmiksi standardikirjastoon. Timsort taas oli yleiskäyttöisin ja nopein vakaa lajittelualgoritmi. Counting sort osoittautui hyvin tehokkaaksi, kun taulukon alkiot voivat saada rajatun määrän eri arvoja.