Erilaisten lajittelualgoritmien vertailua

Niko Pärssinen

ERILAISTEN LAJITTELUALGORITMIEN VERTAILUA

Kandidaatintutkielma

Informaatioteknologian ja viestinnän tiedekunta

Huhtikuu 2021

TIIVISTELMÄ

Niko Pärssinen: Erilaisten lajittelualgoritmien vertailua Kandidaatintutkielma

Tampereen yliopisto

Tietotekniikan kandidaatin tutkinto-ohjelma Huhtikuu 2021

Tässä tutkielmassa vertaillaan viiden erilaisen lajittelualgoritmin nopeuksia, muistin käyttöä sekä vakautta. Nopeutta kuvataan asymptoottisella notaatiolla, joka koostuu iso O-notaatiosta, joka kertoo ylärajan eli hitaimman tapauksen, Omega-notaatiosta, joka kertoo alarajan eli no- peimman tapauksen, ja Theta-notaatiosta, joka kertoo keskiarvon. Muistin käyttö on verratta- vissa, koska osa lajittelualgoritmeista ei käytä ylimääräistä muistia, vaan lajittelee samaan säi- liöön, jossa lajiteltavat jo olivat, ja toiset lajittelualgoritmit lajittelevat uuteen säiliöön. Lajittelu- algoritmin vakaus tarkoittaa sen kykyä pitää samansuuruiset vertailtavat alkuperäisessä jär- jestyksessä. Vertailtavat lajittelualgoritmit ovat lisäyslajittelu, kirjastolajittelu, Shellsort, lomi- tuslajittelu ja kampalajittelu.

Vertailu suoritetaan kahdessa osassa, ensin vertaillaan lisäyslajittelua, kirjastola- jittelua ja Shellsortia keskenään, sillä kaikki kolme käyttää samaa lisäyslajittelun periaatetta.

Toisessa osassa vertaillaan kaikkia keskenään.

Vertailusta selvisi, että lisäyslajittelualgoritmi on yksinkertainen algoritmi, joka ei käytä ylimääräistä muistia ja on vakaa, mutta on myös hitain kaikista. Kirjastolajittelu ja Shellsort laajentavat lisäysalgoritmin periaatetta, mikä tuo lajitteluun nopeutta, mutta kumpikin menettää vakautensa ja kirjastolajittelu lajittelee uuteen säiliöön, joten se on muistin käytössä näistä huonoin. Kampalajittelu on lievästi lisäyslajittelua nopeampi, mutta ei ole vakaa, ja lo- mituslajittelu pystyy samaan nopeuteen kuin kirjastolajittelu, mutta tarvitsee lisää muistia ja on vakaa. Nopeimpia ovat siis kirjastolajittelu ja lomituslajittelu, seuraavaksi nopein on Shellsort ja hitaimpia ovat kampalajittelu ja lisäyslajittelu, joista kampalajittelu on hieman nopeampi.

Avainsanat: Lajittelualgoritmi, asymptoottinen notaatio, lisäyslajittelu, kirjastolajittelu, Shellsort, lomituslajittelu, kampalajittelu

SISÄLLYSLUETTELO

1. JOHDANTO ... 1

2.VERTAILUN PARAMETRIT ... 3

3. LAJITTELUALGORITMIT ... 5

3.1 Lisäyslajittelu... 5

3.1.1 Kirjastolajittelu ... 6

3.1.2 Shellsort ... 7

3.2 Lomituslajittelu ... 9

3.3 Kampalajittelu ... 10

4. VERTAILU ... 12

4.1 Eri lisäyslajitteluiden vertailu ... 12

4.2 Kaikkien lajittelualgoritmien vertailu ... 14

5.YHTEENVETO ... 15

LÄHTEET ... 16

1. JOHDANTO

Lajittelualgoritmit eivät ole missään nimessä uusi asia. Ihmiset ovat historiassa aina laji- telleet jotain, ja kun lajiteltavien määrä kasvaa, tarvitaan tehokas menetelmä, jotta siitä voidaan suoriutua nopeasti. Lajittelualgoritmin tärkeys kuitenkin korostuu vielä entises- tään, kun koneet keksittiin. Koska koneet ovat hyviä suorittamaan yksinkertaisia toistuvia tehtäviä, on niiden toiminnalle tärkeää kehitellä algoritmeja, joilla toistojen määrää voi- daan vähentää ja siten kasvattaa tehokkuutta.

Lajittelualgoritmeja on käsitelty vuosien varsilla valtavasti, mutta niin on aiheen laajuuskin valtava. Tehokkaan lajittelualgoritmin löytäminen on tärkeää eri tilanteisiin, joten aiheen käsitteleminen on tärkeää. Henkilökohtaisena motivaationa aiheen valin- nassa oli tutustua hieman erilaisiin lajittelualgoritmeihin. Quicksortista ja merge sortista eli lomituslajittelusta, ja muutamasta muusta kuulee paljon enemmän. Halusin siis tutus- tua muutamaan entuudestaan itselle vieraaseen lajittelualgoritmiin ja valita mukaan pari tuttua lajittelualgoritmia, lomitus- ja lisäyslajittelu, ja verrata näitä kaikkia keskenään. Li- säyslajittelu on mukana myös sen takia, koska luvuissa 3.1.1 ja 3.1.2 esiteltävät kirjas- tolajittelu ja Shellsort ovat toimintaperiaatteeltaan samanlaisia kuin lisäyslajittelu, joten niitä on mielenkiitoista vertailla keskenään.

Tässä tutkielmassa käsitellään ensin viisi eri lajittelualgoritmia ja sitten vertaillaan niitä keskenään eri parametrien suhteen. Luvussa 2 esitellään, miten algoritmien tehok- kuutta vertaillaan. Luvussa 3 käydään läpi kaikki viisi lajittelualgoritmia, jonka jälkeen luvussa 4 vertaillaan näitä algoritmeja keskenään. Koska valituista algoritmeista kolmella on samanlainen toimintaperiaate, on vertailu jaettu kahteen osaan. Ensin vertaillaan näitä kolmea samanlaista keskenään ja sitten kaikkia viittä keskenään. Luvussa 5 vielä kerrataan vertailun tulokset.

Kaikille lajittelualgoritmeille voidaan määritellä nopeuksien äärirajat, joiden avulla niitä on kätevä vertailla, mutta myös muistin käyttö tulee isoissa tiedon määrissä tärke- äksi. Siksi nopeimman lajittelualgoritmin valitseminen ei aina ole paras vaihtoehto, ja siksi käytännössä saman asian hoitavia algoritmeja on niin useita. Mikään lajittelualgo- ritmi ei ole kaikissa tapauksissa paras.

Vertailusta selvisi, että lomituslajittelu on joukon nopein, mutta kirjastolajittelu on yhtä nopea lukuun ottamatta huonointa tapausta, seuraavaksi nopein on Shellsort ja hi- taimpia ovat kampalajittelu ja lisäyslajittelu, joista kampalajittelu on hieman lisäyslajitte- lua nopeampi. Muistin käytön suhteen kirjasto- ja lomituslajittelu ainoita, jotka tarvitsevat ylimääräistä tilaa. Vakaita lajittelualgoritmeja näistä ovat lomitus- ja lisäyslajittelu.

Tilannekohtaisesti voidaan todeta, että pienillä tiedon määrillä lisäyslajittelu on oi- kein sopiva vaihtoehto, sillä sen hidas nopeus ei merkitse niin paljoa ja se kuitenkin on vakaa eikä tarvitse ylimääräistä muistia. Suuremmilla tiedon määrillä nopeudella on pal- jon enemmän merkitystä, joten kirjasto- ja lomituslajittelu ovat parempia vaihtoehtoja, mutta suuremmilla tiedon määrillä muistin rajallinen käyttö voi olla tärkeää, jolloin kum- pikaan ei ole hyvä vaihtoehto vaan pitää valita esimerkiksi Shellsort.

2. VERTAILUN PARAMETRIT

Lajittelualgoritmien tehokkuutta kuvaa niiden suoritusaika. Tätä kuvataan asymptootti- sella notaatiolla, joka jakautuu kolmeen eri tapaan ilmaista suoritusaikaa. Iso O-notaatio, joka kertoo suoritusajan ylärajan, Omega-notaatio(Ω), joka kertoo alarajan ja Theta-no- taatio(Θ), joka kertoo sekä ylä- että alarajan. Theta-notaatio käytännössä kertoo siis kes- kiarvon. Keskitytään näistä esimerkkinä Theta-notaatioon. [2] Sitä käytetään paljon lajit- telualgoritmien vertailuun, koska sillä pystytään hyvin vertailemaan lajittelualgoritmeja keskenään, koska harvemmin on kyse ääritilanteista.

Θ-notaatio siis ilmaisee, kuinka kauan lajitteluun keskimäärin menee. Tämä il- maistaan matemaattisesti merkinnällä Θ(g(n)), joka tarkoittaa, että lajitteluun menee funktion g(n) verran aikaa riippuen n:stä. Muuttuja n kuvaa lajiteltavien määrää. Nopeu- dessa huomioidaan ainoastaan sen suurin merkitsevä termi ilman vakiokertoimia. Esi- merkiksi Θ(2n²+n) on pelkästään Θ(n²), koska lineaarisen lisääminen neliöön ei muuta sitä merkittävästi.

Nopeimmillaan algoritmi voi suoriutua vakio ajassa eli Ω(1), joka ei ole lajittelual- goritmille käytännössä mahdollista, sillä lajittelualgoritmilla menee vähintään lineaari- sesti aikaa eli O(n) pelkästään jo säiliön kertaalleen läpikäyntiin, vaikka säiliö olisi jo jär- jestyksessä. Tätä astetta hitaampi nopeus on logaritminen eli O(log n), joka on tyypillinen nopeus etsimisalgoritmeille, joiden etsintätyyli perustuu kohdejoukon puolittamiseen joka askeleella, eli muun muassa binäärihaulle. Logaritmista nopeudesta astetta hitaampi on lineaarinen eli O(n). Tällöin nopeus on suoraan verrannollinen kohteiden määrään. Osa lajittelualgoritmeista pystyy parhaassa tilanteessa lineaariseen nopeuteen.

Iso O-notaation tilanteessa puhutaan huonoimmasta tilanteesta, joten lajittelual- goritmeille tyypillinen yläraja on joko O(n log n) tai O(n²). Kaikki, jotka ovat hitaampia kuin O(n²), ovat jo niin hitaita muihin verrattuna, että sellaisia ei kannata edes harkita käyttää. Nopeus O(n²) yleisesti ottaen tarkoittaa, että algoritmi käy säiliön koon n pituisen silmukan sisällä toisen saman pituisen silmukan, eli toisin sanoen algoritmi käy n määrän lajiteltavia n kertaa läpi.

Toinen asia, jonka suhteen lajittelualgoritmeja voidaan verrata on muistin käyttö.

[1] Osa algoritmeista lajittelee kohteet samaan säiliöön, missä ne jo sijaitsivat, kun taas toiset algoritmit kopioivat kohteet toiseen säiliöön. Esimerkiksi O(n) tarkoittaa, että muis- tia tarvitaan lineaarisesti lisää eli saman verran lisää kuin sitä on alun perin. Varsinkin, kun tiedon määrä on valtava, on otettava huomioon tarvittavan muistin määrä.

Kolmas vertailtava parametri on vakaus. [3] Tämä tarkoittaa sitä, että jos esimer- kiksi suuruusjärjestykseen lajiteltaessa mukana on useampia samansuuruisia, vakaa la- jittelualgoritmi pitää samansuuruiset samassa järjestyksessä kuin ne alun perin olivat.

Yksinkertaisten lukujen tai merkkijonojen kohdalla, tämä ei käytännössä merkitse mi- tään, koska samat numerot eivät erotu toisistaan, vaikka niiden järjestys olisi mikä ta- hansa. Mutta jos lajiteltavat kohteet omaavat vertailtavan ominaisuuden lisäksi muita ominaisuuksia, vakaan järjestyksen pitäminen voi olla tärkeää.

3. LAJITTELUALGORITMIT

Lajiteltavia asioita on niin monenlaisia. Siksi myös lajitteluun on kehitelty monenlaisia algoritmeja, jotka kaikki ovat hyviä niissä tilanteissa, joihin ne ovat suunniteltu, mutta eivät välttämättä niin hyviä tilanteissa, joihin niitä ei suunniteltu. Välillä lajiteltavaa on vähän ja välillä taas paljon. Joskus taas muistin rajallinen käyttö tai algoritmin vakaus saattaa olla tärkeämpää kuin lajittelunopeus. Kaikki seuraavat lajittelualgoritmit suoritta- vat lajittelemisen vertailemalla.

3.1 Lisäyslajittelu

Yksinkertaisia lajittelualgoritmeja on muutamia, joista yksi on lisäyslajittelu. Näitä kutsu- taan yksinkertaisiksi, koska niitä pienemmällä koodilla on käytännössä mahdotonta luoda toimivaa lajittelualgoritmia. Lisäyslajittelua käytetään myös monimutkaisemmissa lajittelualgoritmeissa, kuten kirjastolajittelussa ja Shellsortissa, joten ne ovat toimintape- riaateiltaan lisäyslajittelualgoritmeja. [1]

Lisäyslajittelu aloittaa lajittelun listan alusta, jossa se vertaa kahta ensimmäistä.

Jos ne ovat väärässä järjestyksessä, niiden paikat vaihdetaan keskenään. Seuraavaksi kolmatta verrataan sitä edeltävään eli toiseen, jos ne ovat väärässä järjestyksessä niiden paikat vaihdetaan ja kolmannella paikalla ollutta, nyt toisella paikalla olevaa verrataan edeltävään eli ensimmäiseen. Lisäyslajittelu käytännössä siis siirtää kohteen vasem- malle niin paljon, että se on lajiteltu ja sitten siirtyy seuraavaan lajittelemattomaan. To- dellisuudessa se siirtää isomman pois tieltä oikealle, jotta pienempi mahtuu sen isom- man vanhalle paikalle vasemmalle.

Ohjelma 1: Lisäyslajittelu [4]

Hitaimmillaan lisäyslajittelu on O(n²). Parhaassa tapauksessa se pystyy lineaari- seen nopeuteen, mutta tämä käytännössä tarkoittaa sitä, että säiliö oli jo valmiiksi järjes- tyksessä. Keskiarvoltaan lisäyslajittelu on myös Θ(n²), koska vaikka se tekisi joissain kohdissa vähemmän siirtoja, niitä ei huomioida, koska nopeuden suuruusluokka ei muutu. [1] Ohjelmasta 1 voidaan nähdä, että lisäysalgoritmin nopeus tulee sen kahdesta sisäkkäisestä silmukasta eli jokaisen lajiteltavan kohdalla käydään läpi kaikki lajiteltavat siihen asti.

Muistin käytössä lisäyslajittelu on hyvä, koska se lajittelee kohteet samaan säili- öön, missä ne jo ovat. Lisäksi lisäyslajittelu on vakaa algoritmi, sillä kun se törmää tilan- teeseen, jossa on kaksi samansuuruista, se jättää ne paikoilleen. [3]

3.1.1 Kirjastolajittelu

Kirjastolajittelu toimii siis lisäyslajittelualgoritmin periaatteella. Se kuitenkin laajentaa tätä periaatetta lajittelemalla kohteet uuteen säiliöön ja tuomalla lisäyslajittelun rinnalle binää- rihaun, jonka avulla kohde laitetaan oikeaan väliin uudessa säiliössä. Lisäyslajittelualgo- ritmin suuri kompastuskivi nopeudessa on se, että kohteita tarvitsee siirtää aina, kun järjestystä muutetaan. Siirtojen määrä alkaa erityisesti haittaamaan suuremmissa tiedon määrissä. [5]

Kirjastolajittelualgoritmi luo siis uuden säiliön, mutta uusi säiliö on isompi, jotta kohteiden väliin jää tilaa. Lisäyslajittelu tapahtuu vaiheissa ja jokaisessa vaiheessa siir- retään tuplasti enemmän kohteita, kunnes kaikki on siirretty. Eli ensin siirretään kaksi sitten neljä ja niin edelleen. Kohteet siirretään yksitellen ja niille etsitään binäärihaulla paikka uuteen säiliöön. Koska säiliössä on tyhjiä välejä, vähentyy tarve tehdä tilaa, kuten lisäyslajittelualgoritmi joutuu tekemään. Kun yksi vaiheista on ohi, uusi säiliö tasapaino- tetaan uudelleen jakamalla välit taas tasaisesti.

Binäärihaun periaate on se, että aloitetaan puolivälistä, verrataan kohdetta puoli- väliin ja siirrytään oikean puolivälin puoliväliin ja tätä jatketaan, kunnes oikea väli on löy- detty. Sen käyttäminen onnistuu kirjastolajittelussa, koska se tehdään uuteen säiliöön, joka on järjestyksessä.

Ohjelma 2: Kirjastolajittelu (muokattu lähteistä [5] ja [6])

Keskinopeudeltaan kirjastolajittelu on Θ(n log n), koska binäärihakuun menee lo- garitminen määrä aikaa, joka toistetaan n kertaa. Koska kirjastolajittelu lisää jokaisen uuteen säiliöön binäärihaun avulla, vaikka säiliö olisikin jo järjestyksessä, myös parhaa- seen tapaukseen menee Ω(n log n). Pahimmassa tapauksessa nopeus on kuitenkin O(n²), koska jos säiliö on täysin vastakkaisessa järjestyksessä, uuden säiliön väleillä ei ole hyötyä, kun kaikki lisätään aina edellisen viereen. [6]

Muistia tarvitaan saman verran lisää, koska kohteet lajitellaan uuteen säiliöön.

Muistin käyttö on siis O(n). Koska kohteille etsitään oikea väli binäärihaulla, ei ole takuuta siitä, mihin järjestykseen samansuuruiset kohteet ajautuvat, joten kirjastolajittelu ei ole vakaa. [6]

3.1.2 Shellsort

Shellsort puolestaan laajentaa lisäyslajittelualgoritmin periaatetta tuomalla mahdollisuu- den vaihtaa kaukana toisistaan olevia kohteita päittäin. Sen tapa toteuttaa lisäyslajittelu on myös selkeästi erilainen tästä syystä. [7]

Shellsort tapahtuu valitsemalla välin, jonka suuruisella etäisyydellä kohteita ver- rataan. Tätä väliä käytetään jokaisen kohdalla, kunnes vertailun kohde on suuren välin takia säiliön ulkopuolella eli säiliön laajuuden yli. Sitten vaihdetaan pienempään väliin ja jatketaan sama, kunnes sekin ylittää säiliön lopun. Väliä pienennetään, kunnes väli on niin pieni, että vertailu suoritetaan vierekkäisille kohteille, minkä jälkeen säiliön pitäisi olla täysin järjestyksessä. Idea tässä on se, että alussa pystytään siirtämään todella pienet ja todella suuret lähemmäs oikeita paikkojaan paljon nopeammin isoilla hypyillä. Ja myö- hemmin käytetään pienempiä välejä, jotta kohteet saadaan täysin oikeille paikoilleen.

Ohjelma 3: Shellsort (muokattu lähteistä [7] ja [8])

Shellsortin keksijä, Donald Shell, ensin esitti näiden välien olevan n/2, n/4, n/8 ja niin edelleen, kunnes väli on yksi, eli tarkastellaan vierekkäisiä. Tämä tarkoittaa siis sitä, että jos esimerkiksi säiliön koko on 100 ensimmäisen välin kanssa vertaillaan ensim- mäistä ja 51:ttä, sitten toista ja 52:ttä ja niin edelleen. Myöhemmin näitä välejä on paran- nettu ja niille on esitetty useita eri ratkaisuja. Thomas Hibbard esitti välien olevan h_k = 2^k− 1. Esimerkiksi säiliön koolla 100 suurin mahdollinen väli on 63, joka tarkoittaa väliä h₆, jonka jälkeen käytetään väliä h₅= 31 ja niin edelleen aina yhteen asti. [7]

Hitaimmillaan Shellsort on O(n^3/2), keskinopeudeltaan Θ(n^4/3) ja nopeimmillaan Ω(n log n), mutta nopeus riippuu myös hieman välien valinnasta. Shellsort ei käytä yli- määräistä muistia, vaan lajittelee samassa säiliössä. Ja koska kohteita siirretään suurilla etäisyyksillä, samansuuruisten järjestys ei välttämättä säily, joten Shellsort ei ole vakaa.

[3]

3.2 Lomituslajittelu

Lomituslajittelu eli merge sort on hyvin yleisesti käytetty lajittelualgoritmi, jonka toiminta- periaate erottuu aikaisemmin mainituista lisäyslajittelualgoritmeista huomattavasti. Se nimittäin pilkkoo listan ensin yhden pituisiin osiin ja lajittelee sitten listat samalla, kun se yhdistelee niitä.

Lomituslajittelu ensimmäisellä puoliskolla jakaa listan puoliksi ja rekursiivisesti jat- kaa pilkkomalla nämä puolikkaat puoliksi ja niin edelleen, kunnes listat ovat yhden pitui- sia. Tämän jälkeen listoja aletaan yhdistämään siten, että yhdistäessä järjestys tulee huomioitua. Rekursion takia järjestys ei ole ihan tämä, vaan algoritmi aloittaa pilkkomaan ensimmäistä puolta pienemmäksi, kunnes kaksi ensimmäistä lajiteltavaa ovat yhden pi- tuisia listoja, jonka jälkeen se lomittaa ne yhteen ja siirtyy lajittelemaan kaksi seuraavaa ja lomittaa nämä yhteen kahden ensimmäisen kanssa, jonka jälkeen neljä ensimmäistä on lajiteltu ja yhdessä. Tämän jälkeen se tekee saman seuraavalle nelikolle, jonka lajit- telun jälkeen se lomittaa nämä kaksi nelikkoa. Sitten se siirtyy seuraavaan kahdeksaan ja jatkaa tätä niin kauan kuin lajiteltavia riittää. [9]

Ohjelma 4: Lomituslajittelu (muokattu lähteistä [9] ja [10])

Nopeudeltaan lomituslajittelu on Ω(n log n) ja O(n log n) eli sillä on joka tilanteessa sama nopeus. Tämä johtuu siitä, että loimituslajittelu joka tapauksessa pilkkoo listan osiin ja sitten lomittaa sen takaisin kokoon huolimatta siitä, että oliko lista jo valmiiksi lajiteltu. Lomituslajittelu tarvitsee lajittelemiseen ylimääräistä tilaa, sillä alkuperäinen lista jaetaan osalistoihin, joita se käyttää lajittelussa. Lomituslajittelun muistin käyttö on siis O(n) eli se tarvitsee lineaarisesti enemmän tilaa. Se pystyy kuitenkin pitämään saman- suuruiset alkuperäisessä järjestyksessä, joten se on vakaa lajittelualgoritmi. [3]

3.3 Kampalajittelu

Kampalajittelu eli comb sort on toimintaperiaatteeltaan samanlainen kuin kuplalajittelu, joka vertailee kahta vierekkäistä ja vaihtaa paikat tarvittaessa, mutta eroaa lisäyslajitte- lusta siten, että samaa kohdetta ei viedä loppuun asti, vaan yhden vertailun jälkeen jat- ketaan seuraavaan pariin ja sama toistetaan säiliön alusta loppuun, kunnes kaikki ovat järjestyksessä. Kampalajittelu laajentaa tätä periaatetta samalla tavalla kuin Shellsort laajensi lisäyslajittelun periaatetta. Eli ensin verrataan suurempia etäisyyksiä ja pikkuhil- jaa pienennetään vertailtavien etäisyyttä, kunnes kaikki ovat järjestyksessä. [11]

Ohjelma 5: Kampalajittelu (muokattu lähteistä [11] ja [12])

Toisin kuin Shellsortissa, kampalajittelulle ei ole esitetty erilaisia tapoja välin pie- nentämiseen, vaan väliä pienennetään vakiokertoimella jokaisen läpikäynnin jälkeen.

Testaamalla on löydetty k=1,3 olevan ideaalinen kerroin välin pienentämiseen. Eli jos lajiteltavia on 10, ensin käydään vertailut läpi seitsemän välillä, sitten viiden, sitten kol- men, sitten kahden ja viimeiseksi vielä yhden välillä, mikä tarkoittaa vierekkäisiä arvoja.

Koska kampalajittelu vain vaihtaa kohteet päittäin ja sitten jatkaa eteenpäin, se tarvitsee pienemmän kertoimen välin pienentämiseen kuin Shellsort ja siten joutuu myös käymään säiliön läpi useamman kerran kuin Shellsort. [11]

Kampalajittelun nopeus on O(n²) ja keskinopeus on sama, parhaimmassa tilan- teessa nopeus on Ω(n log n). Vaikka kuplalajittelun nopeus on käytännössä sama O(n²), comb sort on silti parannus kuplalajittelusta, ja vaikka nopeus näkyy samana, kampala- jittelu on nopeampi, sillä se pystyy siirtämään pienet arvot isojen päästä nopeammin, mikä on kuplalajittelun suuri kompastuskivi. Ja näin ollen keskinopeus on nopeampi, mutta ei tarpeeksi, että se näkyisi asymptoottisessa suoritusajassa. [12]

Kampalajittelu lajittelee samassa säiliössä, joten lisää muistia ei tarvita. Samaan tapaan kuin Shellsortkin rikkoo järjestyksen siten, että samansuuruiset voivat sekoittua ja vaihtaa järjestystä, joten kampalajittelu ei ole vakaa. [3]

4. VERTAILU

Tässä luvussa vertaillaan luvussa 3 esitellyt lajittelualgoritmit käyttäen luvussa 2 esitel- tyjä parametreja. Lajittelualgoritmien nopeudet ovat suoraan vertailtavissa, mutta pel- kästään nopeuksien perusteella niitä ei voida laittaa paremmuusjärjestykseen. Pelkät nopeudet eivät itsessäänkään ole täysin yksinkertaisia, vaan lajiteltavien määrä ja aloi- tusjärjestys voivat vaikuttaa nopeuteen suurestikin. Tämä vaihtelu ei kuitenkaan näy asymptoottisissa suoritusajoissa, koska sillä kuvataan nopeuden äärirajoja ja keskiar- voa. Kuten kampalajittelu on selkeästi paranneltu versio kuplalajittelusta, mutta niillä on sama keskinopeus Theta-notaatiolla.

Välillä nopeus ei olekaan tärkeintä. Joskus esimerkiksi muistin säästäminen saat- taa olla tärkeämpää. Varsinkin suurilla tiedon määrillä muistin käytöllä voi olla merkitystä.

Tai jos lajiteltavilla on monia ominaisuuksia, joista yhden suhteen on jo lajiteltu, mutta halutaan lajitella jonkin toisen ominaisuuden suhteen, on tärkeää valita vakaa lajittelual- goritmi, joka pystyy pitämään aiemman järjestyksen niiden kesken, joilla on sama lajitel- tava ominaisuus.

Luvussa 4.1 verrataan eri lisäyslajittelualgoritmeja keskenään ja luvussa 4.2 tuo- daan mukaan vertailuun myös lomituslajittelu ja kampalajittelu. Koska lisäyslajittelualgo- ritmeilla on sama toimintaperiaate, on hyvä aloittaa vertaamalla niiden eroja keskenään.

4.1 Eri lisäyslajitteluiden vertailu

Luvussa 3.1 esiteltiin kolme lajittelualgoritmia, joiden kaikkien toimintaperiaate perustuu lisäyslajitteluun. Nämä algoritmit ovat Shellsort, lisäyslajittelu ja kirjastolajittelu. Lisäysla- jittelu on yksinkertainen lajittelualgoritmi ja kirjastolajittelu monimutkaistaa lisäyslajittelua korjatakseen sen kompastuskiven. Shellsort taas käyttää lisäyslajittelua ja parantelee sen ominaisuuksia eri tavalla kuin kirjastolajittelu.

Lisäyslajittelu on siis kaikista yksinkertaisin, ja siksi jääkin nopeudessa taakse muista. Parhaassa tapauksessa se pystyy nopeuteen Ω(n), mutta keskiarvoltaan se on Θ(n²), ja huonoimmassa tilanteessa nopeus on O(n²). Kirjastolajittelu parantaa keskino- peutta tuomalla sen alas nopeuteen Θ(n log n), mutta samalla paras nopeus nousee samaan Ω(n log n). Huonoin tilanne näillä on sama O(n²). Shellsort myös tuo nopeimman ajan ylöspäin nopeuteen Ω(n log n), mutta keskiarvo on Θ(n^4/3) ja huonoin nopeus on O(n^3/2). Koska logaritmia ja murtolukueksponenttia on hankalampaa vertailla noin vain, alla olevassa kuvassa on esitetty n log n, n^4/3 ja n^3/2.

Kuvaajasta 1 voidaan suoraan nähdä, että n^3/2 vaatii selkeästi enemmän askeleita sa- malla lajiteltavien määrällä n kuin toiset käyrät. Askeleiden suorittamiseen kuluu aikaa, joten mitä jyrkempi käyrä, sitä hitaampi nopeus. Toiset kaksi, n log n ja n^4/3 ovatkin paljon lähempänä toisiaan ja n^4/3 on pienillä määrillä nopeampi, mutta jää 94:stä eteenpäin hi- taammaksi kuin n log n. Koska alle sadan lajittelemiseen menee millä tahansa algo- ritmilla niin vähän aikaa, voidaan todeta kirjastolajittelu Shellsortia nopeammaksi.

Muistin rajallisessa käytössä lisäyslajittelu ja Shellsort päihittävät kirjastolajittelun, sillä näistä ainoana kirjastolajittelu lajittelee uuteen säiliöön. Ainoa vakaa näistä lajittelu- algoritmeista on lisäysalgoritmi. Voidaan siis päätellä, että samalla, kun kirjastolajittelu ja Shellsort ovat parannelleet lisäyslajittelua saavuttaakseen suuremman nopeuden, ne kärsivät menettämällä vakautensa ja kirjastolajittelu vielä lisäksi lajittelee uuteen säili- öön.

Lisäyslajittelun ollessa yksinkertainen se suoriutuu pienistä, yksinkertaisista lajit- telutehtävistä oikein hyvin, kun taas suurilla tiedon määrillä sen hidas nopeus alkaa nä- kymään merkittävänä haittana. Suurilla määrillä kirjastolajittelun nopeudesta on hyötyä Shellsortiin ja lisäyslajitteluun verrattuna, mutta jos on kyse todella suurista määristä, kirjastolajittelun tapa lajitella uuteen säiliöön voi olla muistin käytön puolesta haitallista, jolloin Shellsort olisi parempi vaihtoehto.

Kuva 1: Nopeudet n log n, n^4/3 ja n^3/2 havainnollistettu samassa kuvaajassa

4.2 Kaikkien lajittelualgoritmien vertailu

Kampalajittelu on aiempiin verrattuna hyvin lähellä lisäyslajittelun nopeuksia. Parhaassa tapauksessa nopeus on Ω(n log n), ja sekä keskinopeus että huonoin nopeus ovat samat kuin lisäyslajittelulla eli Θ(n²) ja O(n²). Luvussa 3 kuitenkin mainittiin kampalajittelun ole- van nopeampi kuin kuplalajittelu, koska se pystyy siirtämään väärässä päässä olevat arvot oikeaan päähän nopeammin, mutta ero ei ole tarpeeksi merkittävä, että se näkyisi asymptoottisessa notaatiossa. Kampalajittelu on siis hieman lisäyslajittelua nopeampi, mutta hitaampi kuin Shellsort.

Lomituslajittelu on nopeudeltaan tasainen, sillä sen nopeus on aina huonoim- massa ja parhaimmassa tilanteessakin eli O(n log n) ja Ω(n log n). Tämä nopeus on sama kuin kirjastolajittelulla, mutta pahimmassa tapauksessa kirjastolajittelu on hitaampi kuin lomituslajittelu.

Muistin käytössä kampalajittelu on hyvä, sillä se ei lajittele uuteen säiliöön. Lomi- tuslajittelu puolestaan tarvitsee lisää tilaa lajitteluun, joten sen muistin käyttö on O(n).

Lomituslajittelu on vakaa, mutta kampalajittelu ei ole vakaa. Lisäyslajittelu on siis ainoa, joka ei tarvitse ylimääräistä muistia ja on vakaa. Shellsort ja comb sort eivät tarvitse ylimääräistä muistia, eivätkä ole vakaita. Lomituslajittelu tarvitsee ylimääräistä muistia, mutta on vakaa ja kirjastolajittelu tarvitsee ylimääräistä muistia eikä se ole vakaa.

Pienissä tiedon määrissä lisäyslajittelu pärjää ihan hyvin ja vähän suurempia määriä varten lomituslajittelu on yleinen vaihtoehto, sillä se on nopea ja vakaa eikä yli- määräisen muistin käytöllä ole niin suurta väliä. Suurilla määrillä kirjasto- tai lomituslajit- telun nopeus on tärkeää. Suurilla tiedon määrillä voi kuitenkin olla tärkeää rajoittaa muis- tin käyttöä, jolloin kirjasto- ja lomituslajittelu eivät sovellu tähän hyvin vaan on valittava esimerkiksi Shellsort. Kampalajittelun ominaisuudet eivät valitettavasti ole niin loistavat, joten lähes joka tilanteessa jokin muu lajittelualgoritmi on parempi vaihtoehto. Jos tarvit- see lajitella suuria määriä vakaasti ja muistia silmällä pitäen, lisäyslajittelu on ainoa vaih- toehto ja sen hitaan nopeuden takia kannattaa harkita jotain lajittelualgoritmia tämän tut- kielman ulkopuolelta.

5. YHTEENVETO

Tässä tutkielmassa ensin esiteltiin vertailussa käytettävät parametrit ja vertailtavat lajit- telualgoritmit. Sitten vertailu suoritettiin kahdessa osassa, sillä osalla lajittelualgorit- meista on sama toimintaperiaate. Ihan lopussa vielä nopeasti käytettiin vertailun tuloksia tilannekohtaiseen analyysiin. Tutkielmassa mukana olevat lajittelualgoritmit ovat lisäys- lajittelu, kirjastolajittelu, Shellsort, lomituslajittelu ja kampalajittelu. Vertailussa verrattiin algoritmien tehokkuuksia käyttäen asymptoottista notaatiota ja lisäksi huomioitiin niiden muistin käyttö ja vakaus.

Lisäysalgoritmi on joukon hitain, mutta ainoa, joka kykenee lineaariseen nopeu- teen optimaalisessa tilanteessa, kampalajittelulla on käytännössä sama nopeus kuin li- säyslajittelulla. Seuraavaksi nopein on Shellsort ja nopeimpia ovat kirjasto- ja lomitusla- jittelu. Lisäyslajittelu on ainoa, joka ei tarvitse ylimääräistä muistia ja on vakaa. Shellsort ja comb sort eivät tarvitse ylimääräistä muistia, mutta eivät ole vakaita. Lomitus- ja kir- jastolajittelu tarvitsevat ylimääräistä muistia ja lomituslajittelu on vakaa, mutta kirjastola- jittelu ei.

Nopeutensa takia lisäyslajittelu on hyvä vain pienillä lajittelumäärillä ja koska se on vakaa eikä tarvitse ylimääräistä muistia, se on erinomainen vaihtoehto silloin, kun lajitel- tavia on vähän. Suurilla määrillä nopeus on yleensä tärkeää, joten kirjasto- tai lomitusla- jittelu on silloin paras vaihtoehto, mutta suurilla tiedon määrillä muistin rajallinen käyttö voi olla myös tärkeää, jolloin näistä ei kumpikaan sovi. Silloin parempi vaihtoehto on Shellsort. Valitettavasti kampalajittelu jää toiseksi joka aspektissa.

LÄHTEET

[1] Sedgewick, R., Wayne, K., (2011). Algorithms, Fourth Edition. Saatavilla (viitattu 17.3.2021): https://learning.oreilly.com/library/view/algorithms-fourth-edi-

tion/9780132762564/

[2] Ahmad, I., (2020). 40 Algorithms Every Programmer Should Know. Saatavilla (viitattu 17.3.2021): https://learning.oreilly.com/library/view/40-algorithms- every/9781789801217/

[3] Wikipedia (2021) Sorting algorithms. Saatavilla (viitattu 17.3.2021):

https://en.wikipedia.org/wiki/Sorting_algorithm

[4] Wikipedia (2021) Insertion sort. Saatavilla (viitattu 17.3.2021): https://en.wikipe- dia.org/wiki/Insertion_sort

[5] Faujdar N., Ghrera S. P., A detailed experimental analysis of library sort algo- rithm, 2015 Annual IEEE India Conference (INDICON), New Delhi, India, 2015, s. 1-6, doi: https://doi.org/10.1109/INDICON.2015.7443165

[6] Wkipedia (2021) Library sort. Saatavilla (viitattu 18.3.2021): https://en.wikipe- dia.org/wiki/Library_sort

[7] West Chester University (2021) Shellsort & Algoritmic Comparisons. Saatavilla (viitattu 18.3.2021): https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html [8] Wkipedia (2021) Shellsort. Saatavilla (viitattu 18.3.2021): https://en.wikipe-

dia.org/wiki/Shellsort

[9] Parvez F. (2020) Merge Sort Using C, C++, Java, and Python | What is Merge Sort and Examples of it? Saatavilla (viitattu 19.3.2021): https://www.mygreat- learning.com/blog/merge-sort/

[10] Wikipedia (2021) Merge sort. Saatavilla (viitattu 19.3.2021): https://en.wikipe- dia.org/wiki/Merge_sort

[11] GeeksforGeeks (2021) Comb sort. Saatavilla (viitattu 20.3.2021):

https://www.geeksforgeeks.org/comb-sort/

[12] Wkipedia (2021) Comb sort. Saatavilla (viitattu 20.3.2021): https://en.wikipe- dia.org/wiki/Comb_sort