SkillForge | ATLAS

Insertion Sort

15 min read

Insertion Sort

Einführung

Du spielst ein Kartenspiel und sortierst deine Karten auf der Hand. Jede neue Karte, die du ziehst, fügst du an die richtige Stelle ein – manchmal vorne, manchmal in der Mitte, manchmal ganz hinten.

Insertion Sort: Karten an der richtigen Stelle einfügen
Unsortiert vs. sortiertes Einfügen — Bildrechte: Ausbildung-in-der-IT.de (KI-unterstützt)

Ohne es zu merken, führst du dabei schon einen Sortieralgorithmus aus.

Genau dieses Vorgehen bildet die Grundlage von Insertion Sort. Der Algorithmus funktioniert nach demselben Prinzip: Elemente werden Schritt für Schritt an der richtigen Position eingefügt.

Lernziele

Nach dieser Einheit kannst du:

  • Den Algorithmus Insertion Sort in eigenen Worten erklären und die Grundidee beschreiben.
  • Ein gegebenes Array schrittweise mit Insertion Sort sortieren und die einzelnen Zwischenschritte nachvollziehen.
  • Eine korrekte Implementierung in Java schreiben und verstehen, wie die einzelnen Teile des Codes zusammenwirken.
  • Den Algorithmus mit anderen Sortierverfahren vergleichen und entscheiden, wann Insertion Sort sinnvoll eingesetzt werden kann.

Überleitung

Um zu verstehen, wie das funktioniert, schauen wir uns nun die Frage an: Was ist Insertion Sort genau?

Was ist Insertion Sort?

Insertion Sort ist ein Sortierverfahren, das Elemente nacheinander an die richtige Position in eine bereits sortierte Teilliste einfügt. Der Algorithmus arbeitet in-place, das heißt ohne zusätzliche Hilfslisten in signifikanter Größe.

Warum Insertion Sort?

Insertion Sort ist leicht zu verstehen und stabil, also erhält gleiche Werte ihre Reihenfolge. Er ist besonders effizient bei kleinen Datenmengen und fast sortierten Listen.

Verwenden, wennEher nicht verwenden, wenn
Liste ist klein (z. B. < 20 Elemente)Liste ist sehr groß (viele Tausend Elemente)
Daten sind fast sortiertDaten sind stark durchmischt
Stabilität wichtig istMaximale Geschwindigkeit wichtiger ist

Küchen-Metapher

Um die Grundidee greifbar zu machen, schauen wir uns ein Beispiel aus dem Alltag an. Stell dir vor, du räumst deine Gewürze alphabetisch ins Regal ein. Jede neue Dose wird an die richtige Stelle eingefügt, und die anderen rücken bei Bedarf nach rechts.

Dein systematisches Vorgehen:

  1. “Oregano” kommt ins leere Regal – steht allein
  2. “Basilikum” gehört VOR Oregano → Oregano rutscht nach rechts
  3. “Zimt” gehört HINTER Oregano → wird rechts davon platziert
  4. “Curry” gehört zwischen Basilikum und Oregano → beide rutschen nach rechts
  5. “Pfeffer” gehört zwischen Oregano und Zimt → Zimt rutscht nach rechts

Endergebnis: [Basilikum, Curry, Oregano, Pfeffer, Zimt]

Grundidee & Begriffe

Wir betrachten die Liste als zwei Bereiche: links sortiert, rechts unsortiert. In jedem Schritt nimmst du das erste Element aus unsortiert und fügst es in sortiert korrekt ein.

[sortiert] | [unsortiert]
      ^         ^ erstes Element wird entnommen → in [sortiert] einfügen

Dieser Blick auf zwei Bereiche macht das Vorgehen transparent. Du siehst jederzeit, wo eingefügt und wo noch gesucht wird.

Beispiel

Damit du die Vorgehensweise besser nachvollziehen kannst, bauen wir das Beispiel Schritt für Schritt auf. Wir sortieren das Array [12, 3, 7, 1, 9, 4]

Der erste Schlüssel ist 3, weil das erste Element im sortierten Bereich standardmäßig das allererste Listenelement ist (hier 12). Der Algorithmus beginnt immer beim zweiten Element (Index 1), also wird 3 als erstes zu sortierendes Element ausgewählt.

  • Schritt 1: Schlüssel = 3 → 3 < 12, also 12 nach rechts verschieben.

    • Ergebnis: [3, 12, 7, 1, 9, 4]
      • (Sortiert: [3, 12] | Unsortiert: [7, 1, 9, 4])

  • Schritt 2: Schlüssel = 7 → 7 < 12, aber > 3, also zwischen 3 und 12 einfügen.

    • Ergebnis: [3, 7, 12, 1, 9, 4]
      • (Sortiert: [3, 7, 12] | Unsortiert: [1, 9, 4])

  • Schritt 3: Schlüssel = 1 → kleiner als alle Werte links, alles nach rechts verschieben.

    • Ergebnis: [1, 3, 7, 12, 9, 4]
      • (Sortiert: [1, 3, 7, 12] | Unsortiert: [9, 4])

  • Schritt 4: Schlüssel = 9 → 9 < 12, aber > 7, also zwischen 7 und 12 einfügen.

    • Ergebnis: [1, 3, 7, 9, 12, 4]
      • (Sortiert: [1, 3, 7, 9, 12] | Unsortiert: [4])

  • Schritt 5: Schlüssel = 4 → 4 > 3, aber < 7, also zwischen 3 und 7 einfügen.

    • Ergebnis: [1, 3, 4, 7, 9, 12]
      • (Sortiert: [1, 3, 4, 7, 9, 12] | Unsortiert: [])

Am Ende ist der unsortierte Bereich leer. Das Array ist vollständig sortiert.

Java-Implementierung: Schritt für Schritt

In diesem Abschnitt entwickeln wir den Insertion Sort Schritt für Schritt im Java-Code. Dabei fügen wir nach und nach neue Bestandteile hinzu und erklären jeweils, was ergänzt wurde und warum.

Schritt 1: Klassenskelett und Ausgabemethode

public class InsertionSort {
    static void arrayAusgeben(int[] array) {
        for (int wert : array) {
            System.out.print(wert + " ");
        }
        System.out.println();
    }
}

Erklärung:

  • public class InsertionSort legt die Klasse an.
  • arrayAusgeben gibt alle Werte des Arrays aus.
  • So können wir die Inhalte eines Arrays leicht kontrollieren.

Damit haben wir eine Klasse mit einer Hilfsmethode erstellt, die uns erlaubt, den Inhalt eines Arrays zu sehen. Das ist die Grundlage, um später die Zwischenschritte der Sortierung sichtbar zu machen.

Java-Implementierung: Schritt für Schritt

Schritt 2: Äußere Schleife hinzufügen

public class InsertionSort {
    static void arrayAusgeben(int[] array) {
        for (int wert : array) System.out.print(wert + " ");
        System.out.println();
    }
 
    static void insertionSort(int[] zahlen) {
        for (int i = 1; i < zahlen.length; i++) {  // äußere Schleife
            // hier folgt gleich der Einfügeprozess
        }
    }
}

Erklärung:

  • Die Methode insertionSort wird angelegt.
  • Die for-Schleife durchläuft alle Elemente ab Index 1.
  • Damit definieren wir die Grundlage des Sortiervorgangs.

Wir haben also die Sortiermethode mit einer Schleife ergänzt, die jedes Element Schritt für Schritt bearbeitet. Dadurch schaffen wir die Struktur, in die wir den Sortierprozess einsetzen können.

Java-Implementierung: Schritt für Schritt

Schritt 3: Schlüssel und Startposition setzen

public class InsertionSort {
    static void arrayAusgeben(int[] array) {
        for (int wert : array) System.out.print(wert + " ");
        System.out.println();
    }
 
    static void insertionSort(int[] zahlen) {
        for (int i = 1; i < zahlen.length; i++) {
            int key = zahlen[i];   // aktuelles Element
            int pos = i - 1;       // Start im sortierten Teil
            // hier folgt gleich das Verschieben
        }
    }
}

Erklärung:

  • key speichert das aktuelle Element.
  • pos zeigt auf die Position links davon.
  • Damit ist klar, welches Element einsortiert wird und wo der Vergleich beginnt.

Damit haben wir die Variablen vorbereitet, die für jeden Durchlauf nötig sind. Wir wissen nun, welches Element einsortiert wird und an welcher Stelle wir mit dem Vergleichen starten.

Java-Implementierung: Schritt für Schritt

Schritt 4: Verschieben größerer Elemente

public class InsertionSort {
    static void arrayAusgeben(int[] array) {
        for (int wert : array) System.out.print(wert + " ");
        System.out.println();
    }
 
    static void insertionSort(int[] zahlen) {
        for (int i = 1; i < zahlen.length; i++) {
            int key = zahlen[i];
            int pos = i - 1;
            // Alle größeren Werte nach rechts schieben
            while (pos >= 0 && zahlen[pos] > key) {
                zahlen[pos + 1] = zahlen[pos];
                pos--;  // wandere nach links
            }
            // hier folgt gleich das Einfügen
        }
    }
}

Erklärung:

  • Solange links größere Werte stehen, werden sie nach rechts verschoben.
  • Durch pos-- bewegen wir uns schrittweise nach links.
  • So wird die Einfügeposition freigeräumt.

Wir haben also den Teil ergänzt, der Platz für das aktuelle Element schafft. Alle größeren Elemente werden nach rechts verschoben, bis die passende Stelle frei ist.

Java-Implementierung: Schritt für Schritt

Schritt 5: Schlüssel einfügen

public class InsertionSort {
    static void arrayAusgeben(int[] array) {
        for (int wert : array) System.out.print(wert + " ");
        System.out.println();
    }
 
    static void insertionSort(int[] zahlen) {
        for (int i = 1; i < zahlen.length; i++) {
            int key = zahlen[i];
            int pos = i - 1;
            while (pos >= 0 && zahlen[pos] > key) {
                zahlen[pos + 1] = zahlen[pos];
                pos--;
            }
            zahlen[pos + 1] = key;  // an freier Stelle einsetzen
        }
    }
}

Erklärung:

  • Nach dem Verschieben setzen wir key an die freie Position.
  • Damit ist der Einfügevorgang vollständig.

An dieser Stelle haben wir den Schlüssel an die richtige Position gesetzt. Damit wird das aktuelle Element korrekt in den sortierten Teil eingefügt.

Java-Implementierung: Schritt für Schritt

Schritt 6: Test mit main

public class InsertionSort {
    static void arrayAusgeben(int[] array) {
        for (int wert : array) System.out.print(wert + " ");
        System.out.println();
    }
 
    static void insertionSort(int[] zahlen) {
        for (int i = 1; i < zahlen.length; i++) {
            int key = zahlen[i];
            int pos = i - 1;
            while (pos >= 0 && zahlen[pos] > key) {
                zahlen[pos + 1] = zahlen[pos];
                pos--;
            }
            zahlen[pos + 1] = key;
        }
    }
 
    public static void main(String[] args) {
        int[] daten = {12, 3, 7, 1, 9, 4};
        System.out.println("Vor dem Sortieren:");
        arrayAusgeben(daten);
        insertionSort(daten);
        System.out.println("Nach dem Sortieren:");
        arrayAusgeben(daten);
    }
}

Erklärung:

  • In der main-Methode legen wir ein Testarray an.
  • Wir geben es vor und nach dem Sortieren aus.
  • Damit prüfen wir die Funktion des Algorithmus.
⏳ Lädt Dataview-Inhalt...

Vorteile und Nachteile

Die Stärken und Schwächen von Insertion Sort lassen sich übersichtlich in einer Tabelle darstellen:

VorteileNachteile
Einfach zu verstehen und zu implementierenLangsam bei großen Datenmengen (Ø/Worst Case O(n²))
Intuitiv – ähnelt natürlichem SortierenViele Verschiebungen bei umgekehrt sortierten Arrays
Effizient bei kleinen Datenmengen (< 50 Elemente)Nicht geeignet für sehr große Datenmengen
Adaptiv – bei fast sortierten Daten sehr schnell
Stabil – gleiche Werte behalten Reihenfolge
In-Place – benötigt keinen zusätzlichen Speicher
Online-Sortierung möglich

Zeitkomplexität verstehen

Die Laufzeit von Insertion Sort hängt stark von der Reihenfolge der Eingabedaten ab. Die folgende Tabelle zeigt die verschiedenen Szenarien:

SzenarioZeitkomplexitätErklärung
Bester FallO(n)Das Array ist bereits sortiert. Es sind nur Vergleiche notwendig, kein Verschieben.
Durchschnittlicher FallO(n²)Die Elemente liegen zufällig verteilt. Es müssen sowohl viele Vergleiche als auch Verschiebungen durchgeführt werden.
Schlechtester FallO(n²)Das Array ist umgekehrt sortiert. Jedes Element muss an den Anfang verschoben werden, was die maximale Anzahl an Operationen erfordert.

Speicherkomplexität: O(1) – Es wird nur ein konstanter zusätzlicher Speicherplatz benötigt.

Zur Erklärung: Das n steht für die Anzahl der Elemente. Im besten Fall muss jedes Element nur einmal angeschaut werden → O(n). Im schlechtesten Fall muss jedes Element mit allen vorherigen verglichen und verschoben werden → O(n²).

Damit wird deutlich, dass Insertion Sort bei kleinen oder fast sortierten Arrays effizient arbeitet, aber bei großen und ungeordneten Arrays schnell ineffizient wird.

Praktische Anwendungsfälle

Im Folgenden siehst du typische Szenarien, in denen Insertion Sort in der Praxis eingesetzt wird.

  • Highscore-Listen in Spielen: Neue Punktzahlen werden sofort an der richtigen Stelle einsortiert, ohne die ganze Liste neu zu sortieren.
  • Aufräumen kleiner Listen in mobilen Apps: Kleine Datenmengen lassen sich mit Insertion Sort schnell und unkompliziert ordnen.
  • Echtzeit-Sortierung während der Eingabe (z. B. Live-Suche): Neue Eingaben werden sofort einsortiert, sodass die Ergebnisse immer aktuell sind.
  • Hybrid-Algorithmen wie Timsort: Insertion Sort wird für kleine Teilarrays verwendet, da er dort besonders effizient ist.
⏳ Lädt Dataview-Inhalt...

Zusammenfassung

Zusammenfassung:

Funktionsweise von Insertion Sort

Insertion Sort ist ein einfaches, stabiles Sortierverfahren. Du nimmst dabei jedes Element der unsortierten Liste und fügst es an der richtigen Stelle in die sortierte Teilliste ein.

  • Arbeitet in-place, benötigt also keinen zusätzlichen Speicher.
  • Stabile Sortierung: Gleiche Werte behalten ihre Reihenfolge.
  • Besonders effizient für kleine oder fast sortierte Listen.

Schrittweises Vorgehen am Beispiel

Der Algorithmus wird verständlich, wenn du eine Liste in einen sortierten und einen unsortierten Bereich aufteilst. Schritt für Schritt wird das erste Element des unsortierten Bereichs einsortiert.

  • Beispiel mit [12, 3, 7, 1, 9, 4]: Elemente werden der Reihe nach verschoben und eingefügt.
  • Am Ende bleibt kein unsortierter Bereich mehr übrig.

Java-Implementierung in Schritten

Die Umsetzung in Java erfolgt in kleinen, nachvollziehbaren Schritten.

  • Klasse und Hilfsmethode: Eine Klasse InsertionSort mit arrayAusgeben zum Ausgeben von Arrays.
  • Äußere Schleife: Bearbeitet alle Elemente ab Index 1.
  • Schlüsselvariable: Das aktuelle Element wird als key gespeichert.
  • Verschieben: Alle größeren Elemente werden nach rechts verschoben.
  • Einfügen: key wird an die freigewordene Position eingesetzt.
  • Test: In main wird ein Beispielarray sortiert und vor/nach der Sortierung ausgegeben.

Wann Insertion Sort verwenden?

Insertion Sort eignet sich nicht für alle Situationen. Du solltest den Algorithmus gezielt einsetzen.

  • Verwenden, wenn: Die Liste klein ist, die Daten fast sortiert sind oder Stabilität wichtig ist.
  • Nicht verwenden, wenn: Die Liste sehr groß oder stark durchmischt ist.

Vorteile und Nachteile

Die Stärken und Schwächen lassen sich klar gegenüberstellen.

  • Vorteile: Einfach zu implementieren, effizient bei kleinen Datenmengen, adaptiv bei fast sortierten Daten, stabil, in-place, online sortierbar.
  • Nachteile: Langsam bei großen oder stark unsortierten Datenmengen (O(n²)), viele Verschiebungen im Worst Case.

Zeit- und Speicherkomplexität

Die Effizienz hängt von der Eingabereihenfolge ab.

  • Bester Fall: O(n), bereits sortierte Liste.
  • Durchschnitt und Worst Case: O(n²), zufällig verteilt oder umgekehrt sortiert.
  • Speicherbedarf: O(1), da kein zusätzlicher Speicher benötigt wird.

Vergleich zu anderen Algorithmen

Im Vergleich zu komplexeren Algorithmen wie Quicksort oder Mergesort ist Insertion Sort langsamer bei großen Datenmengen. In Hybridverfahren (z. B. Timsort) wird er aber für kleine Teilarrays genutzt, da er dort besonders effizient ist.

Praktische Anwendungsfälle

Insertion Sort wird in der Praxis in mehreren Szenarien genutzt.

  • Highscore-Listen: Neue Werte sofort korrekt einsortieren.
  • Mobile Apps: Ordnung kleiner Datenmengen.
  • Echtzeitanwendungen: Online-Sortierung während der Eingabe.
  • Hybrid-Algorithmen: Teilkomponente von Timsort und ähnlichen Verfahren.

Graphansicht

Backlinks