Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Kandidaatintutkielmat
  • Näytä viite
  •   Etusivu
  • Trepo
  • Kandidaatintutkielmat
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Quicksortin, insertion sortin ja heap sortin toteutustapojen vertailu

Matalamäki, Mimmi Emilia (2019)

 
Avaa tiedosto
matalamaki.pdf (965.8Kt)
Lataukset: 



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
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
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.
Kokoelmat
  • Kandidaatintutkielmat [9818]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste