Heapsort
Zet de lijst om in een heap, een boom waarin elke ouder groter is dan zijn kinderen. Daarna verplaatst het steeds opnieuw de grootste waarde naar het einde.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- nee
- ja
Beste geval: hoe de tijd groeit met de lijstgrootte n als de invoer voor dit algoritme het makkelijkst is.
Gemiddeld: de gewone groei van de tijd met n. Bij n² duren twee keer zoveel waarden ongeveer vier keer zo lang. n log n groeit veel trager.
Slechtste geval: de groei bij de moeilijkste invoer. Handig als de snelheid nooit mag inzakken.
Geheugen: hoeveel extra geheugen nodig is naast de lijst. 1 betekent een paar variabelen, n een kopie van de lijst.
Stabiel: twee gelijke waarden houden hun oorspronkelijke volgorde. Belangrijk als je records op één veld sorteert.
Zonder extra geheugen: sorteert in de lijst zelf, zonder tweede lijst.
- wordt vergeleken
- wordt verplaatst
- op definitieve plek
Probeer dit: Kies een omgekeerde lijst. De heap opbouwen kost bijna geen verwisselingen, daarna zet elke ronde de grootste waarde achteraan.
Hoe het werkt
De heap staat in de lijst zelf: de waarde op plek i heeft zijn kinderen op de plekken 2i+1 en 2i+2. De grootste waarde staat altijd vooraan. Verwissel die naar het einde, maak de heap één kleiner en herstel hem. Het gesorteerde deel groeit vanaf rechts.
Wanneer het een goede keuze is
Als je snelheid nodig hebt die ook in het slechtste geval goed blijft, zonder extra geheugen, bijvoorbeeld op kleine apparaten. Gemiddeld is het trager dan quicksort, dus het dient vaak als vangnet.