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.

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. 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.

Referanser

Sorteringsalgoritmer