====== Insertionsort ======

Insertionsort funktioniert ähnlich wie das Sortieren von Spielkarten in der Hand. Du nimmst eine Karte nach der anderen und steckst sie an die richtige Stelle in deine bereits sortierte Hand.

===== Algorithmus =====

  - Du gehst das Array von links nach rechts durch, beginnend mit dem zweiten Element (das erste Element gilt als bereits sortiert).
  - Für jedes Element suchst du die richtige Position im schon sortierten Teil links davon.
  - Du verschiebst alle größeren Elemente nach rechts, um Platz zu schaffen.
  - Setze das aktuelle Element an seine richtige Position.
  - Wiederhole das, bis alle Elemente sortiert sind.

===== Beispiel =====

Beispiel:

Array: [5, 2, 4, 6, 1]

Schritt 1: Sortierter Teil: [5], nimm 2 → setze vor 5 → [2, 5, 4, 6, 1]

Schritt 2: Sortierter Teil: [2, 5], nimm 4 → setze zwischen 2 und 5 → [2, 4, 5, 6, 1]

Schritt 3: Sortierter Teil: [2, 4, 5], nimm 6 → bleibt → [2, 4, 5, 6, 1]

Schritt 4: Sortierter Teil: [2, 4, 5, 6], nimm 1 → setze an Anfang → [1, 2, 4, 5, 6]

<code c>

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];       // Das Element, das wir an die richtige Position einfügen wollen
        int j = i - 1;

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

        // Setze das key-Element an die richtige Position
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 4, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Unsortiertes Array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    insertionSort(arr, n);

    cout << "Sortiertes Array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}


</code>

==== Erklärung der wichtigsten Punkte: ====

  * key ist das aktuelle Element, das sortiert werden soll.
  * Die while-Schleife verschiebt alle größeren Elemente nach rechts, um Platz zu schaffen.
  * Nach der Schleife wird key an der richtigen Stelle eingefügt.

{{youtube>JMRU2nh6bfs}}