Insertion Sort

Einführung

Insertion Sort (Einfügesortierung) ist ein einfacher Sortieralgorithmus, der ähnlich wie das Sortieren von Spielkarten funktioniert. Er baut das sortierte Array schrittweise auf, indem er jedes neue Element an die richtige Position in der bereits sortierten Teilsequenz einfügt.

Funktionsweise

1. Initialisierung: Das erste Element wird als sortiert betrachtet.
2. Iteration: Das nächste Element wird mit den bereits sortierten Elementen verglichen.
3. Vergleich und Verschiebung: Größere Elemente werden nach rechts verschoben, um Platz für das aktuelle Element zu schaffen.
4. Einfügen: Das aktuelle Element wird an der gefundenen Position eingefügt.
5. Wiederholung: Dieser Prozess wird für alle Elemente wiederholt, bis das gesamte Array sortiert ist.

Hinweis: Bei jedem Durchgang wird die rote Zahl als gezogene Zahl angesehen und an der richtigen Stelle eingefügt (sic!)

Komplexität

• Zeitkomplexität (Best Case): O(n) – wenn das Array bereits sortiert ist.
• Zeitkomplexität (Average/Worst Case): O(n²) – bei zufälliger oder umgekehrter Reihenfolge.
• Speicherkomplexität: O(1) – es wird kein zusätzlicher Speicher benötigt (in-place).

Java-Implementierung

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            // Verschiebe Elemente, die größer als key sind, nach rechts
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Füge key an der richtigen Position ein
            arr[j + 1] = key;
        }
    }

    // Beispielaufruf
    public static void main(String[] args) {
        int[] data = {12, 11, 13, 5, 6};
        System.out.println("Unsortiert: " + java.util.Arrays.toString(data));
        insertionSort(data);
        System.out.println("Sortiert: " + java.util.Arrays.toString(data));
    }
}