Vorlesung Informatik 2 - Teil B: Theorie
4.16 Heap-Sort
Dieser Sortieralgorithmus wird erst jetzt behandelt, weil er das Verständnis von Bäumen und insbesondere des Heap voraussetzt.
Das Prinzip ist sehr einfach: man schreibt die zu sortierenden Elemente in eine Heap und liest diesen dann aus. Wenn man die Implementierung genau so vornimmt, braucht man allerdings den doppelten Speicherplatz.
In einer verbesserten Implementierung baut sich der Heap im gleichen Array auf, in dem die Daten liegen. Zunächst wird das erste Array Element zur Wurzel des Heap. Dann erweitert man den Heap jeweils um das nächste Array Element und führt einen up-heap Operation durch. Dabei reduziert sich der unsortierte Bereich um jeweils ein Element zum Preis von O(N).
Der Heap-Sort garantiert O(N log N), kann wie gerade beschrieben in-situ implementiert werden aber ist nicht stabil.
Der Haupt-Vorteil des Heap-Sort gegenüber Quicksort ist die Garantie von O(N logN) Komplexität, während Quicksort in Ausnahmefällen zu O(N2) degenerieren kann. Dafür lässt sich der Quicksort wie auch der Merge-Sort besser parallelisieren.