# Shellsort visualisieren: Insertion Sort mit Gap-Sequenz

> Shellsort interaktiv: Insertion Sort über weit entfernte Paare, deren Abstand schrittweise auf 1 sinkt. Mit der Standardfolge O(n^2) im Worst Case.

Adresse: https://marckimmel.de/informatik/sortieralgorithmen/shell-sort
English version: https://marckimmel.de/en/informatik/sortieralgorithmen/shell-sort.md

Verallgemeinerter Insertion Sort: sortiert zuerst weit entfernte Paare, danach immer dichtere.

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.

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.

## Weiter

- [Sortieralgorithmen](https://marckimmel.de/informatik/sortieralgorithmen.md)