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

  1. Du gehst das Array von links nach rechts durch, beginnend mit dem zweiten Element (das erste Element gilt als bereits sortiert).
  2. Für jedes Element suchst du die richtige Position im schon sortierten Teil links davon.
  3. Du verschiebst alle größeren Elemente nach rechts, um Platz zu schaffen.
  4. Setze das aktuelle Element an seine richtige Position.
  5. 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] 

#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;
}

Erklärung der wichtigsten Punkte: