Heapsort

Allikas: Vikipeedia
Mine navigeerimisribale Mine otsikasti
Heapsort
Sorting heapsort anim.gif
Heapsortimist demonstreeriv animatsioon
Algoritmi liik Sortimisalgoritm
Ajaline keerukus halvimal juhul
Ajaline keerukus keskmiselt
Ajaline keerukus parimal juhul (erinevad elemendid) või (võrdsed elemendid)
Mahuline keerukus

Heapsort on sortimisalgoritm, mis sarnaneb valiksortimise algoritmiga. Sarnaselt valiksortimisele jagatakse heapsortis massiiv sorteerimata ja sorditud osaks. Sorteerimata massiivi osast luuakse täiuslik kahendkuhi, millelt eemaldatakse suurim liige. Eemaldatud liikmest saab sorditud massiivi osa esimene element. Eemaldamist jätkatakse, kuni massiiv saab sorditud.[1]

Algoritm[muuda | muuda lähteteksti]

Heapsort algoritmis on järgnevad sammud:[1] [2]

  1. Loo sisendandmetest täiuslik kahendkuhi.
  2. Nüüd suurim liige on kuhja juurelement (massiivi esimene element). Eemalda suurim liige asendades see kuhja viimase liikmega (kuhja viimane liige on massiivi sorteerimata osa viimane element). Kuhja suurus vähenes ühe võrra (eemaldatud kuhja suurimast liikmest sai sorditud massiivi osa esimene element).
  3. Vaheta juurelement oma suurima väärtusega alamtipuga, kuni kuhi vastab kuhja tingimusele (iga tipu väärtus on alamtippude omast suurem või sellega võrdne).
  4. Jätka sammust 2, kuni kuhjas on üks liige.

Näide[muuda | muuda lähteteksti]

Olgu { 6, 5, 3, 1, 8, 7, 2, 4 } massiiv, mida tahame sortida. Kõigepealt kuhjastame massiivi ja siis hakkame sortima.

Heapsorti näide
1. Kuhjastamine
Kuhi Lisatav element Vahetatavad elemendid
null 6
6 5
6, 5 3
6, 5, 3 1
6, 5, 3, 1 8
6, 5, 3, 1, 8 5, 8
6, 8, 3, 1, 5 6, 8
8, 6, 3, 1, 5 7
8, 6, 3, 1, 5, 7 3, 7
8, 6, 7, 1, 5, 3 2
8, 6, 7, 1, 5, 3, 2 4
8, 6, 7, 1, 5, 3, 2, 4 1, 4
8, 6, 7, 4, 5, 3, 2, 1
2. Sortimine
Kuhi Vahetatavad elemendid Eemalda element Sorditud massiiv Selgitus
8, 6, 7, 4, 5, 3, 2, 1 8, 1 Vaheta 8 ja 1 kohad, et eemaldada kuhjast 8.
1, 6, 7, 4, 5, 3, 2, 8 8 Eemalda kuhjast 8 ja lisa sorditud massiivi.
1, 6, 7, 4, 5, 3, 2 1, 7 8 Vaheta 1 ja 7 kohad, sest nad on kuhjas vales järjekorras.
7, 6, 1, 4, 5, 3, 2 1, 3 8 Vaheta 1 ja 3 kohad, sest nad on kuhjas vales järjekorras.
7, 6, 3, 4, 5, 1, 2 7, 2 8 Vaheta 7 ja 2 kohad, et eemaldada kuhjast 7.
2, 6, 3, 4, 5, 1, 7 7 8 Eemalda kuhjast 7 ja lisa sorditud massiivi.
2, 6, 3, 4, 5, 1 2, 6 7, 8 Vaheta 2 ja 6 kohad, sest nad on kuhjas vales järjekorras.
6, 2, 3, 4, 5, 1 2, 5 7, 8 Vaheta 2 ja 5 kohad, sest nad on kuhjas vales järjekorras.
6, 5, 3, 4, 2, 1 6, 1 7, 8 Vaheta 6 ja 1 kohad, et eemaldada kuhjast 6.
1, 5, 3, 4, 2, 6 6 7, 8 Eemalda kuhjast 6 ja lisa sorditud massiivi.
1, 5, 3, 4, 2 1, 5 6, 7, 8 Vaheta 1 ja 5 kohad, sest nad on kuhjas vales järjekorras.
5, 1, 3, 4, 2 1, 4 6, 7, 8 Vaheta 1 ja 4 kohad, sest nad on kuhjas vales järjekorras.
5, 4, 3, 1, 2 5, 2 6, 7, 8 Vaheta 5 ja 2 kohad, et eemaldada kuhjast 5.
2, 4, 3, 1, 5 5 6, 7, 8 Eemalda kuhjast 5 ja lisa sorditud massiivi.
2, 4, 3, 1 2, 4 5, 6, 7, 8 Vaheta 2 ja 4 kohad, sest nad on kuhjas vales järjekorras.
4, 2, 3, 1 4, 1 5, 6, 7, 8 Vaheta 4 ja 1 kohad, et eemaldada kuhjast 4.
1, 2, 3, 4 4 5, 6, 7, 8 Eemalda kuhjast 4 ja lisa sorditud massiivi.
1, 2, 3 1, 3 4, 5, 6, 7, 8 Vaheta 1 ja 3 kohad, sest nad on kuhjas vales järjekorras.
3, 2, 1 3, 1 4, 5, 6, 7, 8 Vaheta 3 ja 1 kohad, et eemaldada kuhjast 3.
1, 2, 3 3 4, 5, 6, 7, 8 Eemalda kuhjast 3 ja lisa sorditud massiivi.
1, 2 1, 2 3, 4, 5, 6, 7, 8 Vaheta 1 ja 2 kohad, sest nad on kuhjas vales järjekorras.
2, 1 2, 1 3, 4, 5, 6, 7, 8 Vaheta 2 ja 1 kohad, et eemaldada kuhjast 2.
1, 2 2 3, 4, 5, 6, 7, 8 Eemalda kuhjast 2 ja lisa sorditud massiivi.
1 1 2, 3, 4, 5, 6, 7, 8 Eemalda kuhjast 1 ja lisa sorditud massiivi.
1, 2, 3, 4, 5, 6, 7, 8 Sorditud ja algoritm lõpetab töö.

Jõudlus[muuda | muuda lähteteksti]

Kahendkuhja loomise ajaline keerukus on . Juurelemendi oma suurima väärtusega alamtipuga vahetamine, kuni kuhi vastab kuhja tingimusele, on ajalise keerukusega . Kokku tuleb heapsorti ajaliseks keerukuseks . See ajaline keerukus on nii keskmisel kui halvimal juhul.[3]

Heapsorti mahuline keerukus on .[4]

Võrdlus teiste sortimisalgoritmidega[muuda | muuda lähteteksti]

Mestimissortimisel ajaline keerukus nii keskmisel kui halvimal juhul on , mahuline keerukus on aga . Seetõttu eelistatakse heapsorti mestimissortimisele, kui sortimiseks kuluv mälumaht on oluline.[3]

Kiirsortimise keskmiseks ajaliseks keerukuseks on , aga üldiselt on see ikkagi kiirem kui heapsort oma väiksema konstantse teguri tõttu. Kiirsortimise halvimaks ajaliseks keerukuseks on aga ja halvimaks mahuliseks keerukuseks . Seetõttu on heapsort parem sortimisalgorim, kui halvim ajaline ja mahuline keerukus on olulised.[3]

Viited[muuda | muuda lähteteksti]

  1. 1,0 1,1 "HeapSort". GeeksforGeek. Vaadatud 29.01.2019.
  2. "Heap Sort Algorithm". Programiz. Vaadatud 29.01.2019.
  3. 3,0 3,1 3,2 Karleigh Moore, Beakal Tiliksew, Gaurav Sharma, Geoff Pillingm, Alex Chumbley, Jimin Khim. "Heap Sort". Brilliant. Vaadatud 29.01.2019.
  4. David Urbina. "Heapsort". Medium, 09.10.2017. Vaadatud 29.01.2019.