Redigerer Haugsortering

[[Fil:Sorting heapsort anim.gif|thumb|Haugsortering]]
Innenfor [[informatikk]]en er '''haugsortering''' en [[Sammenligningsortering|sammenligningsbasert]] [[sorteringsalgoritme]]. Haugsortering er en forbedret versjon av [[utvelgelsesortering]], og på samme måte som denne algoritmen deler den innmatningen i en sortert og en usortert region, og reduserer størrelsen på den usorterte regionen iterativt ved å dra ut de største elementene og flytte dem inn i den sorterte region. Forbedringen består av bruken av [[datastruktur]]en [[haug]] i stedet for en søken etter å finne det maksimale over lineær tid.<ref>{{cite book |first=Steven |last=Skiena |authorlink=Steven Skiena |title=The Algorithm Design Manual |url=https://archive.org/details/algorithmdesignm00skie_772 |publisher=Springer |year=2008 |page=[https://archive.org/details/algorithmdesignm00skie_772/page/n120 109] |chapter=Searching and Sorting |isbn=1-84800-069-3 |quote=[H]eapsort is nothing but an implementation of selection sort using the right data structure.|doi=10.1007/978-1-84800-070-4_4}}<!--DOI for chapter--></ref>

Selv om den er tregere i praksis på de fleste datamaskiner enn en godt implementert [[quicksort]], har den den fordel at den har en bedre kjøretid i det verste tilfelle, på kun [[stor O-notasjon|O]](''n'' log ''n'').

Haugsortering ble oppfunnet av [[J. W. J. Williams]]. Dette var også fødselen av haugen som datastruktur.<ref name="brass">{{cite book |first=Peter |last=Brass |title=Advanced Data Structures |url=https://archive.org/details/advanceddatastru00bras_251 |publisher=Cambridge University Press |year=2008 |isbn=978-0-521-88037-4 |page=[https://archive.org/details/advanceddatastru00bras_251/page/n219 209]}}</ref> Samme år publiserte [[R. W. Floyd]] en forbedret versjon som kunne sortere en tabell [[På-stedet algoritme|på-stedet]], som en fortsetteøse av hans tidligere arbeide på [[tresortering|tresorteringsalgoritmen]].<ref name="brass"/>

==Referanser==
<references/>

{{stubb}}
{{Autoritetsdata}}

[[Kategori:Sorteringsalgoritmer]]