Shell Sort

Vergleichsbasiert

Eine verbesserte Variante des Insertion Sort, die zuerst weit auseinanderliegende Elemente sortiert und den Abstand schrittweise reduziert bis zum finalen Insertion-Sort-Durchgang.

Live-Visualisierung

Komplexität

Bester Fall	O(n log n)
Durchschnitt	O(n log² n)
Schlechtester Fall	O(n²)
Speicherkomplexität	O(1)
Stabiles Sortieren	Nein
In-Place	Ja

Legende

O(1): Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n): Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n): Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²): Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil: Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place: In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert: Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert: Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.

Implementierung

TypeScript-Implementierung — direkt kopierbereit.

function shellSort(arr: number[]): number[] {
  const n = arr.length;
  // Knuths Lückenfolge: 1, 4, 13, 40, 121, ...
  let gap = 1;
  while (gap < n / 3) gap = gap * 3 + 1;

  while (gap >= 1) {
    for (let i = gap; i < n; i++) {
      const temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 3);
  }
  return arr;
}

Wie es funktioniert

Shell Sort ist eine Verallgemeinerung des Insertion Sort. Er führt das Konzept einer „Lückenfolge" ein: Statt benachbarte Elemente zu vergleichen, vergleicht er Elemente mit einem definierten Abstand (Gap). Der Gap beginnt groß (ca. n/2) und schrumpft pro Durchgang (typischerweise nach Knuths Folge: 1, 4, 13, 40, 121 ...), bis der letzte Durchgang ein normaler Insertion Sort (Gap = 1) ist.

Warum es funktioniert: Insertion Sort verschiebt Elemente nur eine Position auf einmal. Shell Sorts große Anfangslücken lassen Elemente weite Strecken in einem Schritt zurücklegen — so ist das Array beim letzten Durchgang bereits nahezu sortiert.

Lückenfolge ist entscheidend: Knuths Folge (unten verwendet) ergibt O(n^1.5) in der Praxis. Ciuras Folge (1, 4, 10, 23, 57, 132, 301, 701) ist empirisch optimal.

Wann verwenden: Eingebettete Systeme mit begrenztem Speicher und ohne Bedarf an Worst-Case-Garantien.

Vergleiche Shell Sort direkt mit einem anderen Algorithmus

Code vergleichen →

Heap Sort Counting Sort