Interaktive Demo
Shellsort-Visualisierung
Shellsort, 1959 von Donald Shell veröffentlicht, verbessert Insertion Sort: Elemente springen zuerst über große Abstände und kommen so schnell in die Nähe ihres Platzes. Der letzte Durchlauf ist ein normaler Insertion Sort auf einem fast sortierten Array.
Der Durchlauf mit Abstand 4 bewegt Elemente schnell weit, deshalb bleibt für den letzten Insertion Sort mit Abstand 1 wenig zu tun.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element
- Kette des aktuellen Abstands
- Einzufügendes Element
- Verglichenes Element
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n log n)
Sortierte Eingabe: Jeder Abstand braucht nur einen Vergleich pro Element.
Mittlerer Fall
≈ O(n1.25)
In Experimenten für Knuths Abstände gemessen; eine genaue Schranke ist nicht bewiesen.
Schlechtester Fall
O(n1.5)
Mit Knuths Abständen 1, 4, 13, 40 … ist der schlechteste Fall n1,5.
Zusätzlicher Speicher
O(1)
Wie bei Insertion Sort wird nur das einzufügende Element zur Seite gelegt.
Stabil
Nein
Sprünge über große Abstände können gleiche Elemente überholen.
In-place
Ja
Elemente werden innerhalb des Arrays verschoben.
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 diese Seite | 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 | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Abstände
Die Abstände stammen aus Donald Knuths Folge 1, 4, 13, 40 …, der größte zuerst. Bei 11 Elementen sind das 4 und 1.
2. Insertion Sort pro Kette
Bei Abstand 4 bilden die Elemente an den Positionen 0, 4, 8 eine Kette, ebenso 1, 5, 9 und so weiter. Jede Kette wird mit Insertion Sort sortiert, ein Element rückt also pro Verschiebung 4 Stellen weiter.
3. Der letzte Abstand ist 1
Der letzte Durchlauf ist ein normaler Insertion Sort. Weil die großen Abstände die meisten Elemente schon nahe an ihren Platz gebracht haben, braucht er nur wenige Verschiebungen.