Shellsort
Verallgemeinerter Insertion Sort: sortiert zuerst weit entfernte Paare, danach immer dichtere.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Pseudocode
1 for gap = n/2 down to 1, gap /= 2
2 for i from gap to n - 1
3 temp = a[i]; j = i
4 while j >= gap and a[j - gap] > temp
5 a[j] = a[j - gap]; j -= gap
6 a[j] = temp
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Shellsort ist eine Verallgemeinerung von Insertion Sort. Statt nur direkte Nachbarn zu vergleichen, sortiert er Elemente, die einen größeren Abstand (Gap) zueinander haben. Mit jeder Phase wird die Gap kleiner, bis sie schließlich 1 erreicht und der letzte Durchlauf einem klassischen Insertion Sort entspricht. Durch das vorgeschaltete Sortieren weit entfernter Paare werden Elemente, die weit von ihrer Zielposition entfernt sind, in großen Sprüngen dorthin bewegt. Die Wahl der Gap-Sequenz (im einfachsten Fall n/2, n/4, …, 1) beeinflusst die Laufzeit erheblich: mit der einfachen Sequenz ergibt sich im Worst Case O(n²), mit besseren Sequenzen wie Sedgewick oder Ciura sinkt der Worst Case auf O(n^{4/3}) oder besser. Shellsort arbeitet in-place mit O(1) Zusatz-Speicher, ist aber nicht stabil, weil Elemente über die Gap-Distanz hinweg getauscht werden.
Komplexität
- Best Case
O(n log n) - Average Case
O(n^{4/3}) - Worst Case
O(n^2) - Zusatz-Speicher
O(1)
Wann verwenden?
Sinnvoll auf mittelgroßen Arrays, wenn ein einfacher in-place Algorithmus reicht und kein O(n log n) Worst-Case nötig ist. Wegen der einfachen Implementierung gelegentlich in Embedded Code oder als Subroutine in komplexeren Algorithmen anzutreffen.