Quicksortin, insertion sortin ja heap sortin toteutustapojen vertailu

Abstract

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.