Insertionsort
Zuletzt aktualisiert
Insertionsort baut das sortierte Array Element für Element auf. Es nimmt das nächste unsortierte Element (den „Schlüssel") und verschiebt jedes größere Element im sortierten Bereich um eine Position nach rechts, dann setzt es den Schlüssel in die Lücke. Genau so sortieren die meisten Menschen ein Blatt Spielkarten. Drücke oben auf Abspielen, um zu sehen, wie jeder Schlüssel eingefügt wird, oder gehe die Verschiebungen einzeln durch.
Insertionsort ist bei kleinen oder fast sortierten Eingaben sehr schnell - es läuft in O(n), wenn die Daten bereits sortiert sind - weshalb viele hybride Sortierverfahren für kleine Teilarrays darauf zurückgreifen.
Zeit- und Platzkomplexität
| Fall | Komplexität | Anmerkungen |
|---|---|---|
| Bester Fall | O(n) | Bereits sortiert |
| Durchschnittlicher Fall | O(n²) | Zufällige Reihenfolge |
| Schlechtester Fall | O(n²) | Umgekehrt sortiert |
| Platz | O(1) | In-place |
| Stabil | Ja | Gleiche Elemente behalten ihre relative Reihenfolge |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Behandle das erste Element als sortierten Bereich der Größe eins. |
| 2 | Nimm das nächste Element als Schlüssel. |
| 3 | Verschiebe jedes sortierte Element, das größer als der Schlüssel ist, um eine Position nach rechts. |
| 4 | Füge den Schlüssel in die geöffnete Lücke ein. |
| 5 | Wiederhole, bis jedes Element eingefügt wurde. |
Durchgerechnetes Beispiel
Sortieren von [5, 2, 4, 1]:
| Durchlauf | Array | Aktion |
|---|---|---|
| Start | [5, 2, 4, 1] | 5 ist der anfängliche sortierte Bereich der Größe eins. |
| 1 | [2, 5, 4, 1] | Schlüssel 2: 5 nach rechts verschieben, 2 am Anfang einfügen. |
| 2 | [2, 4, 5, 1] | Schlüssel 4: 5 nach rechts verschieben, 2 ist kleiner, also stoppen, 4 einfügen. |
| 3 | [1, 2, 4, 5] | Schlüssel 1: 5, 4, 2 nach rechts verschieben, 1 am Anfang einfügen. |
| Fertig | [1, 2, 4, 5] | Alle Elemente eingefügt; das Array ist sortiert. |
Wann Insertionsort verwenden
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
Das Array klein ist (etwa n < 20). | Das Array groß und zufällig angeordnet ist. |
Die Daten bereits fast sortiert sind, was den besten Fall O(n) ergibt. | Du einen garantierten schlechtesten Fall von O(n log n) brauchst. |
Du eine stabile, in-place-Sortierung mit O(1) zusätzlichem Speicher brauchst. | Das Verschieben von Elementen teuer ist, da es viele Verschiebungen durchführt. |
| Daten inkrementell eintreffen und online sortiert bleiben müssen. | Die Eingabe umgekehrt sortiert ist, ihr schlechtester Fall O(n²). |
Insertion Sort-Code
Eine saubere, lauffähige Insertion Sort-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Insertion Sort-Code in Python
Python
1def insertion_sort(a):2 for i in range(1, len(a)):3 key = a[i]4 j = i - 15 # Shift larger elements one slot to the right6 while j >= 0 and a[j] > key:7 a[j + 1] = a[j]8 j -= 19 a[j + 1] = key10 return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)Insertion Sort-Code in JavaScript
JavaScript
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 const key = a[i];4 let j = i - 1;5 // Shift larger elements right to open a slot for key6 while (j >= 0 && a[j] > key) {7 a[j + 1] = a[j];8 j--;9 }10 a[j + 1] = key;11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));Insertion Sort-Code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void insertionSort(int[] arr) {5 for (int i = 1; i < arr.length; i++) {6 int key = arr[i];7 int j = i - 1;8 // Shift larger elements one slot to the right9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 arr[j + 1] = key;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {7, 3, 9, 1, 5, 8, 2};19 System.out.println("Before: " + Arrays.toString(arr));20 insertionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Insertion Sort-Code in C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10 for (size_t i = 1; i < a.size(); ++i) {11 int key = a[i];12 int j = static_cast<int>(i) - 1;13 // Shift larger elements one slot to the right14 while (j >= 0 && a[j] > key) {15 a[j + 1] = a[j];16 --j;17 }18 a[j + 1] = key;19 }20}21
22int main() {23 std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24 std::cout << "Before: ";25 printVec(data);26 insertionSort(data);27 std::cout << "After: ";28 printVec(data);29 return 0;30}Insertion Sort-Code in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void insertionSort(int a[], int n) {9 for (int i = 1; i < n; i++) {10 int key = a[i];11 int j = i - 1;12 // Shift larger elements one slot to the right13 while (j >= 0 && a[j] > key) {14 a[j + 1] = a[j];15 j--;16 }17 a[j + 1] = key;18 }19}20
21int main(void) {22 int data[] = {7, 3, 9, 1, 5, 8, 2};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 insertionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Insertionsort-FAQ
Wie ist die Zeitkomplexität von Insertionsort?
Insertionsort ist im Durchschnitt und im schlechtesten Fall
O(n²), aber O(n) bei einem bereits sortierten oder fast sortierten Array. Es verwendet O(1) zusätzlichen Speicher.Ist Insertionsort stabil?
Ja. Insertionsort verschiebt nur Elemente, die streng größer als der Schlüssel sind, sodass gleiche Elemente sich niemals überholen und ihre relative Reihenfolge erhalten bleibt.
Wann sollte ich Insertionsort verwenden?
Verwende es für kleine Arrays oder Daten, die bereits fast sortiert sind. Wegen seines geringen Overheads und seines adaptiven besten Falls nutzen hybride Algorithmen wie Timsort es für kleine Läufe.
Was ist der Unterschied zwischen Insertionsort und Bubblesort?
Beide sind
O(n²)-Vergleichssortierungen, aber Insertionsort verschiebt Elemente, um eine Lücke für den Schlüssel zu öffnen, während Bubblesort wiederholt benachbarte, falsch geordnete Paare vertauscht. Insertionsort führt in der Regel weniger Schreibvorgänge durch und schneidet in der Praxis besser ab, besonders bei fast sortierten Daten, wo es seinen besten Fall O(n) erreicht.Warum ist Insertionsort bei kleinen Arrays schneller als Mergesort?
Insertionsort hat einen sehr geringen konstanten Overhead und keine Rekursion oder zusätzliche Speicherzuweisung, sodass es bei kleinen Eingaben trotz seiner schlechteren asymptotischen Komplexität die
O(n log n)-Sortierungen schlägt. Genau deshalb wechseln hybride Sortierverfahren wie Timsort und Introsort für kleine Teilarrays zu Insertionsort.Funktioniert Insertionsort besser mit einer verketteten Liste oder einem Array?
Insertionsort wird normalerweise für Arrays geschrieben, wo das Verschieben von Elementen die Hauptkosten ausmacht. Bei einer verketteten Liste vermeidest du das Verschieben, indem du den Knoten an seine Stelle einfügst, aber du verlierst den schnellen wahlfreien Zugriff, sodass das Finden der Einfügestelle pro Element weiterhin lineare Zeit kostet und die Gesamtkosten
O(n²) bleiben.Verwandte Ressourcen
Mehr Visualisierungen
