Interaktive Demo
Smoothsort-Visualisierung
Smoothsort, 1981 von Edsger W. Dijkstra erfunden, ist ein Heapsort, der sich vorsortierten Daten anpasst. Statt eines Heaps verwaltet er einen Wald von Heaps, deren Größen Leonardo-Zahlen sind, und bei sortierten Eingaben muss er kaum etwas bewegen.
Wähle „Sortiert“ als Ausgangsreihenfolge: Kaum etwas bewegt sich. Die Bäume über dem Array zeigen die Heaps; ihre Wurzeln steigen von links nach rechts an.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element im Heap-Wald
- Absinkendes Element
- Verglichenes Kind
- Größeres Element
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n)
Bei sortierten Eingaben muss sich nichts bewegen: Jedes Element kostet nur wenige Vergleiche.
Mittlerer Fall
O(n log n)
Wie bei Heapsort sinkt jedes Element durch etwa log n Ebenen.
Schlechtester Fall
O(n log n)
Die Heaps werden nie tiefer als etwa log n Ebenen.
Zusätzlicher Speicher
O(1)
Die Heaps liegen im Array; die Form des Waldes passt in wenige Variablen.
Stabil
Nein
Vertauschungen zwischen Wurzeln und Kindern überspringen gleiche Elemente.
In-place
Ja
Die Heaps werden innerhalb des Arrays auf- und abgebaut.
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 | 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 diese Seite | 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. Leonardo-Heaps
Die Heaps haben 1, 1, 3, 5, 9, 15 … Elemente: die Leonardo-Zahlen, jede die Summe der beiden davor plus 1. Ein Heap der Ordnung k besteht aus einer Wurzel mit Heaps der Ordnung k − 1 und k − 2 darunter.
2. Den Wald aufbauen
Jedes neue Element wird entweder die neue Wurzel der beiden rechten Heaps oder beginnt einen eigenen Heap. Dann wandert es entlang der Wurzeln nach links und in seinem Heap nach unten, bis die Wurzeln aufsteigen und jede Wurzel das größte Element ihres Heaps ist.
3. Abbauen
Die rechte Wurzel ist immer das größte Element und steht damit schon an ihrer endgültigen Position. Fällt sie weg, werden ihre beiden Teilbäume eigene Heaps, die nur in die Reihe der Wurzeln eingepasst werden müssen.
Quellen
- Smoothsort stellte Edsger W. Dijkstra in seiner Notiz EWD796a vor, „Smoothsort, an alternative for sorting in situ“. Diese Visualisierung folgt seiner Idee, verwaltet die Heaps aber in einer einfachen Liste statt mit Dijkstras kompakter Buchführung.