Haugsortering
Innenfor informatikken er haugsortering en 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 datastrukturen haug i stedet for en søken etter å finne det maksimale over lineær tid.[1]
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 O(n log n).
Haugsortering ble oppfunnet av J. W. J. Williams. Dette var også fødselen av haugen som datastruktur.[2] Samme år publiserte R. W. Floyd en forbedret versjon som kunne sortere en tabell på-stedet, som en fortsetteøse av hans tidligere arbeide på tresorteringsalgoritmen.[2]
Referanser rediger
- ^ Skiena, Steven (2008). «Searching and Sorting». The Algorithm Design Manual. Springer. s. 109. ISBN 1-84800-069-3. doi:10.1007/978-1-84800-070-4_4. «[H]eapsort is nothing but an implementation of selection sort using the right data structure.»
- ^ a b Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. s. 209. ISBN 978-0-521-88037-4.