Treesort

Grundidee und Bedeutung

Treesort ist ein Sortieralgorithmus, den Robert Floyd 1962 vorstellte. Er zählt zu den Vorgängern von Heapsort. Er sortiert die Elemente eines Eingabe-Arrays entsprechend einer totalen Ordnungsrelation „≤“ aufsteigend in ein Ausgabe-Array.

Der Algorithmus verwendet einen Binärbaum als Zwischenspeicher: Die Blätter enthalten die noch nicht ausgegebenen Eingabewerte. In jedem inneren Knoten steht jeweils das kleinere der beiden Kindselemente. Dadurch enthält die Wurzel immer den kleinsten noch vorhandenen Wert. Dieser wird ausgegeben; anschließend wird sein Blatt durch ∞ ersetzt und die betroffenen inneren Knoten werden neu berechnet.

Treesort hat die optimale Laufzeit O(n log n) und benötigt O(n) zusätzlichen Speicher.

Aufbau des Binärbaums

Für n Eingabewerte wird ein Zwischenspeicher mit doppelter Größe der Eingabe angelegt. Die zweite Hälfte wird zunächst mit der unsortierten Eingabe gefüllt und bildet die Blattknoten des als Binärbaum betrachteten Arrays. Die vordere Hälfte enthält die Elternknoten.

Neben dem Sortierschlüssel wird in jedem gespeicherten Eintrag auch die Position des zugehörigen Blatts gespeichert. Beim Aufbau werden die Elternknoten in mehreren Durchläufen mit dem kleineren Wert ihrer beiden Kinder gefüllt. Nach der Ausgabe des Wurzelwerts lässt sich über die gespeicherte Position genau das passende Blatt auf ∞ setzen.

Ablauf im Pseudocode

Die Prozedur Treesort(Unsortiert, n, Sortiert, k) schreibt die kleinsten k Elemente eines n-elementigen Arrays in Sortiert. Das Array m hat die Indizes 1 bis 2n − 1. Zuerst wird für i = 1 bis n jeder Wert mit seiner Blattposition gespeichert: m[n+i−1] := packe(Unsortiert[i−1], n+i−1).

Danach werden die inneren Knoten von i = n−1 bis 1 aufgebaut: m[i] := minimum(m[2i], m[2i+1]). Für jeden der k Durchläufe wird die linke Hälfte von m[1], also der kleinste Wert, in Sortiert[j] geschrieben. Die rechte Hälfte von m[1] liefert die Position i des zugehörigen Blatts. Dieses Blatt wird auf ∞ gesetzt. Von ⌊i div 2⌋ bis zur Wurzel werden anschließend die Minima neu bestimmt.

packe(wert, position) verbindet Wert und Position; linkeHälfte und rechteHälfte lesen beide Bestandteile aus. minimum(x,y) liefert das Minimum der beiden Zahlen.

Beispiel

Beim Eingabe-Array (7, 5, 13, 11, 2, 3) besitzt m elf Elemente. An den Blattpositionen 6 bis 11 stehen (7,6), (5,7), (13,8), (11,9), (2,10) und (3,11). Nach dem Füllen der inneren Knoten ist (2,10) das kleinste Element im Baum. Daher wird 2 zuerst ausgegeben und m[10] auf ∞ gesetzt.

Für k = 6 werden in fünf weiteren Schleifendurchläufen jeweils die verbleibenden kleinsten Elemente ermittelt und in das Ausgabe-Array übertragen.