imported>ⵓ: +https ⇄

2025-12-04T17:12:47Z

+https ⇄

Neue Seite

'''Treesort''' ist ein [[Sortieralgorithmus]], der 1962 vom Informatiker [[Robert Floyd]] vorgestellt wurde und einer der Vorgänger des Algorithmus [[Heapsort]] ist.<ref>[https://xlinux.nist.gov/dads/HTML/treesort2.html ''U.S. National Institute of Standards and Technology – treesort/2''] xlinux.nist.gov – abgerufen am 12. März 2013</ref><ref>{{Literatur |Autor=''[[Robert Floyd|Robert W. Floyd]]'' |Titel=Algorithm 113: Treesort |Sammelwerk=Communications of the ACM |Band=5 |Nummer=8 |Datum=1962-08 |Seiten=434 |Online=[https://s2.smu.edu/~barr/barrlib/pertcpm/ACMp436-wegstein.pdf Online] |Format=PDF |KBytes=725}}</ref>

== Prinzip ==
Treesort erhält ein Eingabe-[[Feld (Datentyp)|Array]] von Elementen und gibt sie in einem Ausgabe-Array in aufsteigender Reihenfolge gemäß ihrer [[Ordnungsrelation#Totalordnung|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 [[Blätter und innere Knoten in der Graphentheorie|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 <math> {O}(n \log n) </math> unter Verwendung von <math>{O}(n)</math> 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 <code>m</code> wird zu Beginn mit der Funktion <code>packe (wert, position)</code> ein Wert zusammen mit seiner Position geschrieben. Mithilfe der Funktionen <code>linkeHälfte</code> und <code>rechteHälfte</code> werden die beiden Werte wieder ausgelesen. Die Funktion <code>minimum (x,y)</code> 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] := <math>\infty</math>
'''für''' i := <math>\lfloor i \div 2\rfloor</math> '''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 <code>m</code> 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 <math>\infty</math> 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.

<gallery widths="410" heights="320">
FloydTreesort initial.svg|Initialisierung
FloydTreesort01.svg|Ermitteln des kleinsten Elements
FloydTreesort02.svg|Schleife: Ermitteln der übrigen kleinsten Elemente
FloydTreesort end.svg|Letzter Schritt
</gallery>

== Einzelnachweise ==
<references />

[[Kategorie:Sortieralgorithmus]]

Treesort - Versionsgeschichte

imported>ⵓ: +https ⇄