Interaktive Demo
Crumsort-Visualisierung
Crumsort von Igor van den Hoven ist ein sehr schneller In-place-Sortieralgorithmus. Seine Fulcrum-Partition nimmt das Pivot aus dem Array und füllt die entstandene Lücke dann immer wieder von beiden Enden, das braucht weniger Schreibzugriffe als Tauschen.
Achte auf die Lücke: Sie springt zwischen dem linken und dem rechten Ende hin und her. Mit „Wenige verschiedene Werte“ siehst du, dass Crumsort nicht stabil ist.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element
- Pivot (aus dem Array genommen)
- ≤ Pivot
- > Pivot
- 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, dank der Fulcrum-Partition mit weniger Schreibzugriffen.
Schlechtester Fall
O(n log n)
Sehr ungleiche Partitionen wechseln zu Quadsort, einem Mergesort.
Zusätzlicher Speicher
O(log n)
Ein fester Puffer von 512 Elementen, dazu der Rekursionsstapel.
Stabil
Nein
Das Füllen von Lücken von beiden Enden ändert die Reihenfolge gleicher Elemente.
In-place
Ja
Die Partition füllt nur Lücken innerhalb 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 | 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 diese Seite | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Analysieren und Pivot wählen
Wie Fluxsort prüft Crumsort zuerst, ob das Array sortiert oder umgekehrt ist. Dann wählt er ein Pivot, hier den Median aus erstem, mittlerem und letztem Element.
2. Die Fulcrum-Partition
Das Pivot wird herausgenommen, am linken Ende entsteht eine Lücke. Von rechts wandert das erste Element ≤ Pivot in diese Lücke, dadurch entsteht rechts eine Lücke. Von links füllt sie das erste Element > Pivot und so weiter, bis sich beide Enden treffen und das Pivot die letzte Lücke füllt.
3. Hier vereinfacht
Diese Visualisierung nutzt eine Lücke von einem Element, wie die Referenzversion im README. Das Original verschiebt 32 Elemente in einen kleinen Zwischenspeicher, um sie ohne Verzweigungen zu vergleichen, nimmt den Pseudomedian aus 9 und sortiert Teile unter 24 Elementen mit Quadsort.
Quellen
- Crumsort stammt von Igor van den Hoven. Die Partition auf dieser Seite folgt der Referenz-Fulcrum-Partition aus seinem README, vereinfacht wie oben beschrieben; das Original findest du unter github.com/scandum/crumsort.