Interaktive Demo
Treesort-Visualisierung
Treesort fügt jedes Element in einen binären Suchbaum ein und liest den Baum dann der Reihe nach aus. Bei zufälligen Eingaben bleibt der Baum flach und die Sortierung schnell, bei sortierten wird er zu einer langen Kette.
Wähle „Sortiert“ oder „Umgekehrt“: Der Baum wird zu einem einzigen langen Ast, der schlechteste Fall.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element im Array
- Einzufügendes Element
- Verglichener Knoten
- Knoten im Baum
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n log n)
Ein ausgeglichener Baum: Jedes Einfügen geht nur etwa log n Ebenen tief.
Mittlerer Fall
O(n log n)
In einem Baum aus zufälligen Eingaben liegt ein Knoten im Mittel etwa 1,4 · log n Ebenen tief.
Schlechtester Fall
O(n²)
Sortierte oder umgekehrte Eingaben machen den Baum zu einer Liste mit n Ebenen.
Zusätzlicher Speicher
O(n)
Jedes Element bekommt einen eigenen Baumknoten.
Stabil
Ja
Gleiche Elemente gehen nach rechts, das Auslesen behält ihre Reihenfolge.
In-place
Nein
Der Baum entsteht außerhalb des Arrays.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort diese Seite | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Binärer Suchbaum
Jeder Knoten hat höchstens zwei Kinder: Alles Kleinere liegt in seinem linken Teilbaum, alles Größere oder Gleiche im rechten.
2. Einfügen
Ein neues Element beginnt an der Wurzel und läuft nach unten, nach links, wenn es kleiner ist, sonst nach rechts, bis es einen freien Platz findet. Gleiche Elemente gehen nach rechts, das hält die Sortierung stabil.
3. Der Reihe nach auslesen
Der Reihe nach ausgelesen (linker Teilbaum, Knoten, rechter Teilbaum) ergibt der Baum alle Elemente sortiert. Wie schnell Treesort ist, hängt von der Tiefe des Baums ab.