Treesort

Treesort ist ein Sortieralgorithmus, der 1962 vom Informatiker Robert Floyd vorgestellt wurde und einer der Vorgänger des Algorithmus Heapsort ist.

Prinzip

Treesort erhält ein Eingabe-Array von Elementen und gibt sie in einem Ausgabe-Array in aufsteigender Reihenfolge gemäß ihrer totalen Ordnungsrelation („≤“) aus. Dafür wird ein Zwischenspeicher der doppelten Größe der Eingabe erstellt, wovon die zweite Hälfte zunächst mit der unsortierten Eingabe befüllt wird. Fasst man das ganze Array als Binärbaum auf, so stellt die hintere Hälfte die Einträge für die Blattknoten dar. Die vordere Hälfte sind die Elternknoten, in die nun in mehreren Durchläufen jeweils der kleinere Wert der beiden Kindsknoten eingetragen wird. Zusätzlich zum Sortierschlüssel wird auch die Position innerhalb der Blattknoten gespeichert. Am Ende eines Durchlaufs wird an der im Wurzelknoten gespeicherten Position der passende Blattknoten durch den Wert unendlich ersetzt. Somit steht nach jedem Durchlauf im Wurzelknoten der niedrigste Wert der Einträge im Binärbaum, der dann ins Ausgabe-Array kopiert wird.

Der Algorithmus verfügt über eine optimale Laufzeit von ${O}(n\log n)$ unter Verwendung von ${O}(n)$ zusätzlichem Speicher.

Pseudocode

Der folgende Code beschreibt den Algorithmus nach Floyd, der die kleinsten k Elemente des n-elementigen Arrays Unsortiert in das k-elementige Array Sortiert schreibt. In den Zwischenspeicher m wird zu Beginn mit der Funktion packe (wert, position) ein Wert zusammen mit seiner Position geschrieben. Mithilfe der Funktionen linkeHälfte und rechteHälfte werden die beiden Werte wieder ausgelesen. Die Funktion minimum (x,y) liefert das Minimum der beiden Zahlen x und y.

 Prozedur Treesort(Unsortiert, n, Sortiert, k)
   m := Array mit Index 1 bis 2n - 1
   für i:= 1 bis n
     m[n+i-1] := packe(Unsortiert[i-1], n+i-1)
   für i:=n-1 bis 1
     m[i] := minimum(m[2i], m[2i+1])
   für j:=1 bis k
     Sortiert[j] := linkeHälfte(m[1])
     i := rechteHälfte(m[1])
     m[i] := $\infty$
     für i := $\lfloor i\div 2\rfloor$ solange i > 0
       m[i] := minimum(m[2i], m[2i+1])

Beispiel

Das Eingabe-Array (7, 5, 13, 11, 2, 3) wird von Treesort zunächst in den Zwischenspeicher mitsamt Position gespeichert. Damit hat das Array m elf Elemente und an den Positionen 6 bis 11 stehen die folgenden Einträge:

• in m[6] steht (7,6)
• in m[7] steht (5,7)
• in m[8] steht (13,8)
• in m[9] steht (11,9)
• in m[10] steht (2,10)
• in m[11] steht (3,11)

Dieser Zustand ist im ersten Bild als Binärbaum dargestellt. Anschließend werden die inneren Knoten von den Blättern zur Wurzel gefüllt und dabei das kleinste Element im Baum ermittelt, also (2,10). Somit wird 2 als erstes Element in das Ausgabe-Array eingetragen und m[10] wird auf $\infty$ gesetzt (zweites Bild). Für k=6 wird in fünf weiteren Schleifendurchläufen nun jeweils das verbleibende kleinste Element ermittelt und ins Ausgabe-Array übertragen.

• 
  Initialisierung
• 
  Ermitteln des kleinsten Elements
• 
  Schleife: Ermitteln der übrigen kleinsten Elemente
• 
  Letzter Schritt