Heapsort
Upptäckare eller uppfinnare | J. W. J. Williams ![]() | |
---|---|---|
Upptäcktsdatum | 1964 ![]() | |
Tidskomplexitet i värsta fall | ![]() | |
Tidskomplexitet i bästa fall | ![]() | |
Tidskomplexitet i medel | ![]() | |
Rumskomplexitet i värsta fall | ![]() |
Heapsort är en instabil sorteringsalgoritm. Den sorterar n objekt med tidskomplexitet i värsta fall. Algoritmen kan ses som en förbättring av urvalssortering där datastrukturen heap utnyttjas för att snabbt kunna välja ut det största elementet i varje steg.[1]
Algoritmen
[redigera | redigera wikitext]Konceptuellt genomför Heapsort två steg. I det första steget byggs en max-heap upp utifrån listan som ska sorteras. Detta kan implementeras som en array som representerar ett binärträd, där det största elementet finns först i arrayen.[2]
I det andra steget så plockas det största elementet ut från heapen och flyttas till slutet av arrayen. Heapstorleken minskar sedan med ett, och den del av arrayen som ingår i heapen uppdateras för att behålla heap-egenskaperna. [2] Detta upprepas fram tills heapen är tom, varpå arrayen är indatan i sorterad ordning.
Tidskomplexitet
[redigera | redigera wikitext]Att bygga upp en heap i en array har tidskomplexitet , för en lista med storlek n. Att uppdatera en heap så att den behåller heap-egenskaperna har tidskomplexitet , för en array med storlek n. I det andra steget i algoritmen så körs uppdateringen en gång för varje element i listan som ska sorteras, vilket ger en total tidskomplexitet på . [2]
Källor
[redigera | redigera wikitext]- ^ Skiena, Steven (2008). The Algorithm Design Manual. sid. 109
- ^ [a b c] H Cormen, Thomas; E Leiserson, Charles; L Rivest, Ronald; Stein, Clifford (2009). Introduction to algorithms. MIT Press. sid. 160. ISBN 9780262033848