Interaktive Demo
Tournamentsort-Visualisierung
Tournamentsort lässt die Elemente ein K.-o.-Turnier austragen, in dem immer das kleinere gewinnt. Der Gesamtsieger ist das kleinste Element. Nachdem er herausgenommen wurde, werden nur die Spiele auf seinem Weg nach oben neu ausgetragen.
Achte auf den farbigen Weg: Wenn ein Sieger geht, werden nur die Spiele auf seinem Weg nach oben neu ausgetragen.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element im Array
- Spieler im Turnier
- Neu ausgetragenes Spiel
- Weg des Siegers
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n log n)
Aufbau und Neuaustragung kosten immer etwa log n Vergleiche pro Element.
Mittlerer Fall
O(n log n)
n − 1 Spiele bauen den Turnierbaum, danach trägt jeder Sieger nur die log n Spiele auf seinem Weg neu aus.
Schlechtester Fall
O(n log n)
Der Turnierbaum ist ausgeglichen, egal wie die Eingabe geordnet ist.
Zusätzlicher Speicher
O(n)
Der Turnierbaum braucht einen Knoten für jedes Spiel.
Stabil
Ja
Bei Gleichstand gewinnt das linke Element, das zuerst kam.
In-place
Nein
Der Turnierbaum 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 | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort diese Seite | 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. Der Turnierbaum
Jedes Element tritt als Blatt an. In jedem Spiel kommt das kleinere von zwei Elementen weiter, nach n − 1 Spielen steht also das kleinste Element ganz oben.
2. Den Sieger herausnehmen
Der Sieger kommt an die nächste Position des Arrays. Sein Blatt ist jetzt leer, jedes Spiel, an dem er teilgenommen hat, muss also neu entschieden werden.
3. Nur einen Weg neu ausspielen
Alle anderen Spiele behalten ihr Ergebnis, pro Element werden also nur etwa log n Spiele neu ausgetragen. Heapsort nutzt dieselbe Idee, speichert seinen Baum aber im Array selbst.