Heapsort

Ordnar listan som en hög, ett träd där varje förälder är större än sina barn. Sedan flyttar den det största värdet till slutet, om och om igen.

bästa fall Ω(n log n)
genomsnitt Θ(n log n)
värsta fall O(n log n)
minne O(1)
inte stabil
utan extra minne

Vad betyder det här?

Bästa fall: hur tiden växer med listans storlek n när indata är den lättaste för den här algoritmen.
Genomsnitt: hur tiden brukar växa med n. Med n² tar dubbla antalet värden ungefär fyra gånger så lång tid. n log n växer mycket långsammare.
Värsta fall: tillväxten på den svåraste indatan. Viktigt när hastigheten aldrig får sjunka.
Minne: hur mycket extra minne som behövs utöver listan. 1 betyder några variabler, n betyder en kopia av listan.
Stabil: två lika värden behåller sin ursprungliga ordning. Viktigt när man sorterar poster efter ett fält.
Utan extra minne: sorterar inuti själva listan, utan en andra lista.

jämförs
flyttas
på slutgiltig plats

0 / 299 steg

Jämförelser Byten

Tryck på Spela upp: linjerna visar hur kostnaden växer

Hastighet 8 steg / s

Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.

Prova det här: Välj en omvänd lista. Högen byggs nästan utan byten, sedan flyttar varje runda det största värdet till slutet.

Så fungerar det

Högen lagras i själva listan: värdet på plats nummer i har sina barn på platserna 2i+1 och 2i+2. Det största värdet ligger alltid först. Byt det till slutet, gör högen en plats mindre och laga den. Den sorterade delen växer från höger.

När det är ett bra val

När du behöver en hastighet som håller även i värsta fall, utan extra minne, till exempel på små enheter. I genomsnitt är den långsammare än quicksort, så den används ofta som reserv.