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.

bester Fall Ω(n log n)
Durchschnitt Θ(n log n)
schlechtester Fall O(n log n)
Speicher O(1)
nicht stabil
ohne Zusatzspeicher

Was bedeutet das?

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

0 / 299 Schritte

Vergleiche Tauschvorgänge

Auf Abspielen drücken: Die Linien zeigen, wie die Kosten wachsen

Geschwindigkeit 8 Schritte / s

Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.

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.