Interaktive Demo
Fluxsort-Visualisierung
Fluxsort von Igor van den Hoven ist einer der schnellsten stabilen Sortieralgorithmen. Er partitioniert wie Quicksort, kopiert die größeren Elemente aber in einen Zwischenspeicher, dadurch behalten gleiche Elemente ihre Reihenfolge.
Wähle „Sortiert“ oder „Umgekehrt“: Die Analyse ist nach einem Durchlauf fertig. Mit „Wenige verschiedene Werte“ siehst du, dass Fluxsort stabil ist.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element
- Pivot
- ≤ Pivot, bleibt im Array
- > Pivot, im Zwischenspeicher
- Verglichenes Paar (kleiner Teil)
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n)
Seine Analyse erkennt sortierte und umgekehrte Eingaben mit n Vergleichen.
Mittlerer Fall
O(n log n)
Partitioniert wie Quicksort, mit sorgfältig gewähltem Pivot.
Schlechtester Fall
O(n log n)
Sehr ungleiche Partitionen wechseln zu Quadsort, einem Mergesort.
Zusätzlicher Speicher
O(n)
Zwischenspeicher für bis zu n Elemente, dazu der Rekursionsstapel.
Stabil
Ja
Elemente behalten ihre Reihenfolge, wenn sie in den Zwischenspeicher und zurück kopiert werden.
In-place
Nein
Größere Elemente wandern in den Zwischenspeicher.
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 | 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 diese Seite | 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. Analysieren
Zuerst prüft Fluxsort, wie geordnet das Array ist. Sortierte Arrays sind fertig, umgekehrte werden umgedreht, beides mit n Vergleichen. Das Original misst außerdem die Ordnung von vier Abschnitten und wechselt bei weitgehend geordneten Daten zu Quadsort, einem Mergesort.
2. In den Zwischenspeicher partitionieren
Elemente bis zum Pivot werden nach vorne ins Array gepackt, größere in den Zwischenspeicher kopiert, beide in ihrer ursprünglichen Reihenfolge. Deshalb ist Fluxsort stabil, anders als Quicksort.
3. Hier vereinfacht
Diese Visualisierung nimmt den Median aus 3 statt des Quasimedians aus 9 als Pivot, kopiert den Zwischenspeicher vor dem Weitermachen zurück und sortiert Teile mit bis zu 3 Elementen direkt. Das Original sortiert Teile unter 96 Elementen mit Quadsort und hat weitere Absicherungen.
Quellen
- Fluxsort stammt von Igor van den Hoven. Diese Seite zeigt eine vereinfachte Version nach seiner Beschreibung; das Original und seine Dokumentation findest du unter github.com/scandum/fluxsort.