Heapsort
Ordnet die Liste als Heap an, also als Baum, in dem jeder Wert größer ist als seine Kinder. Dann bringt es immer wieder den größten Wert ans Ende.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- nein
- ja
Bester Fall: wie die Zeit mit der Listengröße n wächst, wenn die Eingabe für diesen Algorithmus am einfachsten ist.
Durchschnitt: das übliche Wachstum der Zeit mit n. Bei n² dauern doppelt so viele Werte etwa viermal so lang. n log n wächst viel langsamer.
Schlechtester Fall: das Wachstum bei der schwierigsten Eingabe. Wichtig, wenn das Tempo nie einbrechen darf.
Speicher: wie viel Zusatzspeicher neben der Liste nötig ist. 1 heißt ein paar Variablen, n heißt eine Kopie der Liste.
Stabil: Zwei gleiche Werte behalten ihre ursprüngliche Reihenfolge. Wichtig, wenn man Datensätze nach einem Feld sortiert.
Ohne Zusatzspeicher: sortiert direkt in der Liste, ohne zweite Liste.
- wird verglichen
- wird verschoben
- am endgültigen Platz
Probieren Sie es aus: Wählen Sie eine umgekehrte Liste. Der Heap entsteht fast ohne Tausch, dann bringt jede Runde den größten Wert ans Ende.
So funktioniert es
Der Heap steckt in der Liste selbst: Der Wert an Platz i hat seine Kinder an den Plätzen 2i+1 und 2i+2. Der größte Wert steht immer vorne. Er wird ans Ende getauscht, dann wird der Heap um eins kleiner und repariert. So wächst der sortierte Teil von rechts.
Wann es sich eignet
Wenn es auch im schlechtesten Fall schnell bleiben soll und kein Zusatzspeicher da ist, etwa auf kleinen Geräten. Im Durchschnitt ist es langsamer als Quicksort. Deshalb dient es oft als Ersatz, falls Quicksort zu langsam wird.