Haugsortering

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk
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 | rediger kilde]

  1. ^ 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.» 
  2. ^ a b Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. s. 209. ISBN 978-0-521-88037-4. 
informatikkstubbDenne informatikkrelaterte artikkelen er foreløpig kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.