Insertion Sort Algorithmus in Java: Klares Beispiel & Schritt-für-Schritt-Anleitung

Was ist der Insertion Sort Algorithmus?

Insertion Sort ist eine einfache Sortiertechnik, ideal für kleine oder fast sortierte Datensätze. In jeder Iteration entfernt das Algorithmus ein Element, vergleicht es mit den vorherigen Elementen und fügt es an der richtigen Position ein.

Insertion Sort arbeitet im schlimmsten und durchschnittlichen Fall in O(n²), erreicht aber lineare Performance, wenn das Array bereits sortiert ist. Es ist ein In-Place, stabiler Sortieralgorithmus, der nur konstanten zusätzlichen Speicher benötigt.

Insertion Sort Algorithmus Prozess

Hier ist eine visuelle Darstellung des Insertion Sort Workflows:

Insertion Sort Algorithmus Prozess

Java-Programmbeispiel zum Sortieren eines Arrays mit Insertion Sort:

package com.guru99;
public class InsertionSortBeispiel {
    public static void main(String a[]) {
        int[] meinArray = {860, 8, 200, 9};
        System.out.println("Vor Insertion Sort");
        printArray(meinArray);
        insertionSort(meinArray); // Array mit Insertion Sort sortieren
        System.out.println("Nach Insertion Sort");
        printArray(meinArray);
    }
    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("Sortierdurchlauf Nummer " + (i));
            int key = arr[i];
            int j = i - 1;
            while ((j > -1) && (arr[j] > key)) {
                System.out.println("Vergleiche " + key + " und " + arr[j]);
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            System.out.println("Elemente getauscht: Neues Array nach Tausch");
            printArray(arr);
        }
    }
    static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

Code-Ausgabe:

Vor Insertion Sort
860 8 200 9
Sortierdurchlauf Nummer 1
Vergleiche 8 und 860
Elemente getauscht: Neues Array nach Tausch
8 860 200 9
Sortierdurchlauf Nummer 2
Vergleiche 200 und 860
Elemente getauscht: Neues Array nach Tausch
8 200 860 9
Sortierdurchlauf Nummer 3
Vergleiche 9 und 860
Vergleiche 9 und 200
Elemente getauscht: Neues Array nach Tausch
8 9 200 860
Nach Insertion Sort
8 9 200 860