Algorithmusgratis

Insertion Sort

Sortiere ein Array, indem du einen sortierten Anfang Element für Element erweiterst.

Zeit: O(n²)
Speicher: O(1)

// Schritt für Schritt

Schritt 1 / 15

1function insertionSort(nums) {2  for (let i = 1; i < nums.length; i++) {3    const key = nums[i];4    let j = i - 1;5    while (j >= 0 && nums[j] > key) {6      nums[j + 1] = nums[j];7      j--;8    }9    nums[j + 1] = key;10  }11  return nums;12}

key: = 2

Nimm key = 2. Alles links davon ist bereits sortiert.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

So funktioniert es

Nimm das nächste Element als Schlüssel. Schiebe jedes größere Element im sortierten Anfang eine Stelle nach rechts und setze den Schlüssel in die Lücke. Im schlechtesten Fall ist das quadratisch, aber bei kurzen oder fast sortierten Arrays sehr schnell. Deshalb nutzen echte Sortierverfahren es für kleine Abschnitte.