Quicksortin, insertion sortin ja heap sortin toteutustapojen vertailu
Matalamäki, Mimmi Emilia (2019)
Matalamäki, Mimmi Emilia
2019
Tietotekniikka
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2019-01-07
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201901251150
https://urn.fi/URN:NBN:fi:tty-201901251150
Tiivistelmä
Järjestysalgoritmeilla on merkittävä rooli tietotekniikassa, koska monet algoritmit tarvitsevat syötteitään järjestyksessä tai algoritmien tarvitsee järjestää tietoja suorituksensa aikana. Tässä työssä tutkitaan kolmea eri järjestysalgoritmia. Tutkittavat järjestysalgoritmit ovat quicksort, insertion sort ja heap sort. Työn tavoitteena on selvittää mitkä ovat näiden kolmen järjestysalgoritmin suurimpia eroja algoritmien toteutustasolla.
Työ on toteutettu suurimmaksi osaksi kirjallisuustutkimuksena. Kirjallisuustutkimus esittelee jokaisen algoritmin toiminnan ja toteutuksen. Algoritmien asymptoottisen suoritusajan vertailussa on käytetty laadullista tutkimusta, kun on laskettu algoritmien suorittamien operaatioiden määriä parhaimmassa, keskimääräisessä ja pahimmassa tapauksessa.
Tutkimuksessa selvisi, että algoritmien toimintalogiikat eroavat toisistaan huomattavasti. Siinä missä quicksort ja insertion sort lajittelevat saamansa syötteen, heap sort luo syötteestä uuden tietorakenteen (maksimi- tai minimikeon) ja järjestää sen. Vaikka quicksortin ja heap sortin toimintalogiikat eroavat suuresti toisistaan, ovat ne molemmat epävakaita algoritmeja ja insertion sort on vakaa algoritmi. Heap sortin asymptoottinen suoritusaika on aina nlogn ja quicksortin ja insertion sortin asymptoottinen suoritusaika riippuu siitä, onko kyseessä paras, keskimääräinen vai pahin tapaus.
Työ on toteutettu suurimmaksi osaksi kirjallisuustutkimuksena. Kirjallisuustutkimus esittelee jokaisen algoritmin toiminnan ja toteutuksen. Algoritmien asymptoottisen suoritusajan vertailussa on käytetty laadullista tutkimusta, kun on laskettu algoritmien suorittamien operaatioiden määriä parhaimmassa, keskimääräisessä ja pahimmassa tapauksessa.
Tutkimuksessa selvisi, että algoritmien toimintalogiikat eroavat toisistaan huomattavasti. Siinä missä quicksort ja insertion sort lajittelevat saamansa syötteen, heap sort luo syötteestä uuden tietorakenteen (maksimi- tai minimikeon) ja järjestää sen. Vaikka quicksortin ja heap sortin toimintalogiikat eroavat suuresti toisistaan, ovat ne molemmat epävakaita algoritmeja ja insertion sort on vakaa algoritmi. Heap sortin asymptoottinen suoritusaika on aina nlogn ja quicksortin ja insertion sortin asymptoottinen suoritusaika riippuu siitä, onko kyseessä paras, keskimääräinen vai pahin tapaus.
Kokoelmat
- Kandidaatintutkielmat [7051]