Sortieralgorithmen

Selection Sort, Insertion Sort & Analyse

Vorlesung 11 | Fortgeschrittene Algorithmen

Ordnung ins Chaos bringen

Lernziele

Verstehen, warum Sortieren wichtig ist
Selection Sort implementieren und verstehen
Insertion Sort implementieren und verstehen
Algorithmen analysieren und vergleichen
Stabilität von Sortieralgorithmen verstehen
Die richtige Wahl für verschiedene Situationen treffen

Warum ist Sortieren wichtig?

Praktische Anwendungen

Telefonbuch (nach Namen)
Suchergebnisse (nach Relevanz)
Highscore-Listen (nach Punkten)
Dateien (nach Datum/Größe)
Datenbanken (Indizes)

Algorithmische Vorteile

Schnellere Suche: Binäre Suche möglich
Duplikate finden: Nebeneinander!
Median finden: Mittleres Element
Visualisierung: Bessere Darstellung

Das Sortierproblem

Eingabe

64

25

12

22

11

Ausgabe (aufsteigend sortiert)

11

12

22

25

64

Ziel: Elemente so umordnen, dass arr[0] ≤ arr[1] ≤ ... ≤ arr[n-1]

Selection Sort - Die Idee

Algorithmus in Worten

Finde das kleinste Element im unsortierten Teil
Tausche es mit dem ersten Element des unsortierten Teils
Wiederhole für den Rest des Arrays

Analogie: Wie wenn Sie Spielkarten sortieren, indem Sie immer die kleinste Karte suchen und nach vorne legen.

Selection Sort - Schritt für Schritt

Start:

64

25

12

22

11

Finde Minimum (11), tausche mit 64

Nach Schritt 1:

11

25

12

22

64

Finde Minimum (12), tausche mit 25

Nach Schritt 2:

11

12

25

22

64

Finde Minimum (22), tausche mit 25

Selection Sort - Der Code

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Finde Index des Minimums
        int minIdx = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

        // Tausche arr[i] mit arr[minIdx]
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}
            

Selection Sort - Analyse

Vergleiche zählen

Durchgang 1: n-1 Vergleiche

Durchgang 2: n-2 Vergleiche

...

Durchgang n-1: 1 Vergleich

Gesamt:

(n-1) + (n-2) + ... + 1

= n(n-1)/2

≈ n²/2

Eigenschaften

Zeitkomplexität: O(n²) - wobei n = Anzahl der Elemente
Tausche: Genau n-1
In-place: Ja (kein Extra-Speicher nötig)
Stabil: ❌ Nein (siehe nächste Folie!)

Vorteil: Minimale Anzahl an Tauschen (gut wenn Schreiben teuer ist)

💾 Was bedeutet "In-place"?

Definition: In-place Algorithmus

Ein Sortieralgorithmus ist In-place, wenn er keinen zusätzlichen Speicher benötigt (außer ein paar Variablen). Das Array wird direkt vor Ort sortiert.

✅ In-place: Ja

void selectionSort(int arr[], int n) {
    int minIndex, temp;  // Nur 2 Variablen!
    for (int i = 0; i < n-1; i++) {
        minIndex = i;
        // Sortieren direkt im Array
        // Kein Extra-Array nötig!
    }
}
                        

Speicherverbrauch:

O(1) - konstant!

Egal ob n=10 oder n=1.000.000, wir brauchen nur 2-3 Extra-Variablen

❌ Nicht In-place

void mergeSort(int arr[], int n) {
    // Braucht ein zweites Array!
    int temp[n];  // Extra-Speicher ⚠️

    // Merge benötigt zusätzliches
    // Array zum Zusammenführen
}
                        

Speicherverbrauch:

O(n) - linear!

Bei n=1.000.000 Elementen brauchen wir ein zweites Array mit 1.000.000 Plätzen!

                    🎯 Warum ist In-place wichtig?
                    Speichereffizienz: Wichtig bei großen Datenmengen oder begrenztem RAM
Embedded Systems: Mikrocontroller haben oft nur wenige KB RAM
Performance: Weniger Speicherzugriffe = schneller
Beispiele: Selection Sort, Insertion Sort, Bubble Sort sind alle In-place

                

📖 Was bedeutet "Stabil" vs. "Instabil"?

Definition: Stabilität bei Sortieralgorithmen

Ein Sortieralgorithmus ist stabil, wenn gleiche Elemente nach dem Sortieren ihre ursprüngliche relative Reihenfolge beibehalten.

✅ Stabiler Algorithmus

Vorher:
[5a, 3, 5b, 1, 2]

Nachher:
[1, 2, 3, 5a, 5b]

✓ Die Reihenfolge der beiden 5er bleibt erhalten:
5a kommt vor 5b (wie im Original)

❌ Instabiler Algorithmus

Vorher:
[5a, 3, 5b, 1, 2]

Nachher:
[1, 2, 3, 5b, 5a]

✗ Die Reihenfolge wurde vertauscht:
Jetzt kommt 5b vor 5a!

Warum ist das wichtig?

Wenn Sie nach mehreren Kriterien sortieren wollen (z.B. erst nach Name, dann nach Alter), brauchen Sie einen stabilen Algorithmus! Sonst geht die erste Sortierung verloren.

⚠️ Warum ist Selection Sort NICHT stabil?

Problem: Lange Tauschoperationen zerstören die Reihenfolge

Beispiel: Sortiere [3a, 5, 3b, 1, 2]

Schritt 1: Finde Minimum (1) an Position 3
Tausche Position 0 ↔ Position 3: [1, 5, 3b, 3a, 2]
❌ Die beiden 3er haben jetzt die Reihenfolge getauscht!

Schritt 2: Finde Minimum (2) an Position 4
Tausche Position 1 ↔ Position 4: [1, 2, 3b, 3a, 5]

Fertig: [1, 2, 3b, 3a, 5]
❌ 3b kommt jetzt vor 3a (war ursprünglich umgekehrt!)

Grund: Beim Tauschen über große Distanzen können gleiche Elemente ihre relative Position verlieren!

📊 Warum O(n²) Vergleiche?

n = Anzahl der Elemente im Array

Beispiel: Array mit n=5 Elementen

Runde i	Vergleiche
0	4 (n-1)
1	3 (n-2)
2	2 (n-3)
3	1 (n-4)
Summe	10

Formel:

Vergleiche = (n-1) + (n-2) + (n-3) + ... + 1

= n × (n-1) / 2
(Gauß'sche Summenformel)

≈ n² / 2
Für große n dominiert n²

Beispiel n=5: 5 × 4 / 2 = 10 ✓

Wichtig: Die Komplexität ist O(n²), weil der Term n² für große n am stärksten wächst!

Insertion Sort - Die Idee

Algorithmus in Worten

Nimm das nächste Element aus dem unsortierten Teil
Finde die richtige Position im sortierten Teil
Schiebe größere Elemente nach rechts
Füge das Element an der richtigen Stelle ein

Analogie: Wie Karten sortieren beim Kartenspiel - neue Karte an richtige Stelle in der Hand einfügen.

Insertion Sort - Schritt für Schritt (Teil 1)

🔹 Schritt 0: Start - Array mit 5 Elementen

64

25

12

22

11

Wichtig: Das erste Element (64) gilt als bereits sortiert.

Grün = sortierter Bereich | Weiß = unsortierter Bereich

🔹 Schritt 1: Füge 25 ein

64

25

12

22

11

Was passiert?

Speichere key = 25 (das aktuelle Element)
Vergleiche: 25 < 64? ✓ Ja!
Schiebe 64 eine Position nach rechts (von Index 0 → 1)
Füge 25 an Position 0 ein

25

64

12

22

11

Ergebnis: Jetzt sind die ersten 2 Elemente sortiert!

Insertion Sort - Schritt für Schritt (Teil 2)

🔹 Schritt 2: Füge 12 ein

25

64

12

22

11

Was passiert?

Speichere key = 12
Vergleiche: 12 < 64? ✓ Ja! → Schiebe 64 nach rechts (Index 2 → 3)
Vergleiche: 12 < 25? ✓ Ja! → Schiebe 25 nach rechts (Index 1 → 2)
Keine weiteren Elemente links → Füge 12 an Position 0 ein

12

25

64

22

11

🔹 Schritt 3: Füge 22 ein

12

25

64

22

11

Speichere key = 22
Vergleiche: 22 < 64? ✓ Ja! → Schiebe 64 nach rechts
Vergleiche: 22 < 25? ✓ Ja! → Schiebe 25 nach rechts
Vergleiche: 22 < 12? ✗ Nein! → Stopp
Füge 22 an Position 1 ein (zwischen 12 und 25)

12

22

25

64

11

Insertion Sort - Schritt für Schritt (Teil 3)

🔹 Schritt 4: Füge 11 ein (Letztes Element)

12

22

25

64

11

Was passiert?

Speichere key = 11
Vergleiche: 11 < 64? ✓ Ja! → Schiebe 64 nach rechts
Vergleiche: 11 < 25? ✓ Ja! → Schiebe 25 nach rechts
Vergleiche: 11 < 22? ✓ Ja! → Schiebe 22 nach rechts
Vergleiche: 11 < 12? ✓ Ja! → Schiebe 12 nach rechts
Keine weiteren Elemente → Füge 11 an Position 0 ein

11

12

22

25

64

✅ Fertig! Das Array ist vollständig sortiert.

🔑 Kernprinzip von Insertion Sort:

Schritt für Schritt: Wir nehmen jedes Element und fügen es an der richtigen Stelle im bereits sortierten Teil ein
Schieben: Alle größeren Elemente werden nach rechts verschoben, um Platz zu machen
Effizienz: Bei fast sortierten Arrays sehr schnell! (Nur wenige Verschiebungen nötig)

Insertion Sort - Der Code

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];      // Element zum Einfügen
        int j = i - 1;

        // Schiebe größere Elemente nach rechts
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Füge key an richtiger Stelle ein
        arr[j + 1] = key;
    }
}
            

Insertion Sort - Analyse

Zeitkomplexität

Worst Case: Array ist umgekehrt sortiert

→ O(n²) Vergleiche und Verschiebungen

Best Case: Array ist bereits sortiert

→ O(n) - nur n-1 Vergleiche!

Average Case: O(n²)

Eigenschaften

In-place: Ja
Stabil: Ja!
Adaptiv: Ja (schnell bei fast sortierten Daten)
Online: Ja (kann Element für Element sortieren)

Ideal für: Kleine Arrays oder fast sortierte Daten

Stabilität von Sortieralgorithmen

Definition

Ein Sortieralgorithmus ist stabil, wenn Elemente mit gleichem Schlüssel ihre relative Reihenfolge behalten.

Beispiel: Nach Alter sortieren

Eingabe: (Anna, 25), (Bob, 30), (Clara, 25)

Stabil:

(Anna, 25), (Clara, 25), (Bob, 30)

Anna bleibt vor Clara!

Nicht stabil:

(Clara, 25), (Anna, 25), (Bob, 30)

Reihenfolge von Anna/Clara geändert!

Vergleich: Selection Sort vs. Insertion Sort

Eigenschaft	Selection Sort	Insertion Sort
Best Case	O(n²)	O(n)
Worst Case	O(n²)	O(n²)
Tausche/Verschiebungen	O(n)	O(n²)
Stabil	Nein	Ja
Adaptiv	Nein	Ja

Zur Erinnerung: Bubble Sort

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Tausche Nachbarn
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
            

Eigenschaften: O(n²), stabil, in-place

Kann optimiert werden mit "swapped"-Flag für O(n) Best Case

Die drei einfachen Sortieralgorithmen

Bubble Sort

Idee: Tausche benachbarte Elemente

Gut für: Pädagogik, kleine Arrays

Nachteil: Viele Tausche

Selection Sort

Idee: Finde Minimum, setze ans Ende

Gut für: Wenn Schreiben teuer

Nachteil: Immer O(n²)

Insertion Sort

Idee: Füge an richtiger Stelle ein

Gut für: Fast sortierte Daten

Nachteil: O(n²) worst case

In der Praxis: Insertion Sort ist meist der beste der drei!

Wann welchen Algorithmus?

Kleine Arrays (n < 20)

→ Insertion Sort - einfach, geringe Konstante

Fast sortierte Daten

→ Insertion Sort - O(n) im Best Case!

Schreibzugriffe minimieren

→ Selection Sort - nur n-1 Tausche

Stabilität wichtig

→ Insertion Sort oder Bubble Sort

Große Arrays

→ Effizientere Algorithmen wie Quicksort oder Mergesort (O(n log n))

Absteigend sortieren

Aufsteigend (Standard)

if (arr[j] > arr[j+1]) {
    // tausche
}
                    

11

22

33

Absteigend

if (arr[j] < arr[j+1]) {
    // tausche
}
                    

33

22

11

Einfach: Nur den Vergleichsoperator umdrehen!

Quiz

Welcher Algorithmus ist das?

for (i = 1; i < n; i++) {
    key = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = key;
}
                

A) Bubble Sort

B) Selection Sort

C) Insertion Sort

Quiz Lösung

Antwort: C) Insertion Sort

Erkennungsmerkmale:

key = arr[i] - speichert Element zum Einfügen
While-Schleife schiebt Elemente nach rechts
arr[j+1] = key - fügt an richtiger Stelle ein

Zum Vergleich:

Selection Sort hat minIdx und sucht das Minimum

Bubble Sort vergleicht arr[j] mit arr[j+1]

Komplettes Beispiel

#include <stdio.h>

void druckeArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = 5;

    printf("Vorher: ");
    druckeArray(arr, n);

    insertionSort(arr, n);

    printf("Nachher: ");
    druckeArray(arr, n);

    return 0;
}
            

Bubble Sort - Wie funktioniert es?

Prinzip: Die größten Elemente "blubbern" nach oben

Vergleiche benachbarte Elemente und tausche sie, wenn sie in falscher Reihenfolge sind. Wiederhole das, bis keine Tauschvorgänge mehr nötig sind.

✅ Vorteile

Sehr einfach zu verstehen
Stabil
In-Place (kein extra Speicher)
Kann früh abbrechen wenn sortiert

❌ Nachteile

Sehr langsam: O(n²)
Viele Vergleiche
Viele Tauschoperationen
In Praxis kaum verwendet

Bubble Sort - Implementation

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  // Flag für Optimierung

        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Tausche benachbarte Elemente
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }

        // Wenn keine Tauschvorgänge: Array ist sortiert!
        if (!swapped) {
            break;
        }
    }
}
            

💡 Optimierung: Das swapped-Flag erlaubt frühzeitiges Abbrechen, wenn das Array bereits sortiert ist!

🚀 Bubble Sort Optimierung: Das "swapped"-Flag

Warum brauchen wir das "swapped"-Flag?

Problem: Ohne Optimierung läuft Bubble Sort immer n-1 Durchgänge, auch wenn das Array bereits sortiert ist!

❌ Ohne Optimierung

void bubbleSortBasic(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
        // Läuft IMMER weiter!
    }
}
                        

Bei sortiertem Array [1,2,3,4,5]:

• Durchgang 1: 4 Vergleiche, 0 Tausche

• Durchgang 2: 3 Vergleiche, 0 Tausche

• Durchgang 3: 2 Vergleiche, 0 Tausche

• Durchgang 4: 1 Vergleich, 0 Tausche

Gesamt: 10 Vergleiche = O(n²) 😢

✅ Mit swapped-Flag

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;  // Flag zurücksetzen
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = 1;  // Tausch erfolgt!
            }
        }
        if (!swapped) break; // Fertig!
    }
}
                        

Bei sortiertem Array [1,2,3,4,5]:

• Durchgang 1: 4 Vergleiche, 0 Tausche

• swapped == 0 → BREAK!

Gesamt: 4 Vergleiche = O(n) 🎉

📊 Komplexität mit swapped-Flag:

Best Case (sortiertes Array): O(n) - nur ein Durchgang! 🚀
Average Case: O(n²) - viele Tausche nötig
Worst Case (umgekehrt sortiert): O(n²) - jeder Durchgang tauscht

💡 Fazit: Das swapped-Flag macht Bubble Sort adaptiv - es passt sich an bereits sortierte Daten an. Ohne Flag ist Bubble Sort immer O(n²), egal wie gut die Eingabe ist!

Stabilität - Warum ist das wichtig?

Was bedeutet "stabil"?

Ein Sortieralgorithmus ist stabil, wenn gleiche Elemente ihre relative Reihenfolge behalten.

✅ Stabil (Insertion Sort)

Vorher: [(3, A), (5, B), (3, C), (1, D)]
Nachher: [(1, D), (3, A), (3, C), (5, B)]

Die beiden 3er behalten ihre Reihenfolge: A vor C

❌ Instabil (Selection Sort)

Vorher: [(3, A), (5, B), (3, C), (1, D)]
Nachher: [(1, D), (3, C), (3, A), (5, B)]

Die beiden 3er haben Reihenfolge getauscht: C vor A

Stabilität in der Praxis

Beispiel: Sortierung von Studenten

Studenten nach Note sortieren - bei gleicher Note soll die alphabetische Reihenfolge erhalten bleiben:

Unsortiert

Anna:    2.3
Bernd:   1.7
Clara:   2.3
Daniel:  1.0
Emma:    2.3

Sortiert (stabil)

Daniel:  1.0
Bernd:   1.7
Anna:    2.3  ← Reihenfolge
Clara:   2.3  ← bleibt
Emma:    2.3  ← erhalten!

💡 Wichtig: Wenn Sie nach mehreren Kriterien sortieren wollen (z.B. erst nach Name, dann nach Note), brauchen Sie einen stabilen Algorithmus!

Performance-Vergleich: Real World

Laufzeiten für verschiedene Array-Größen

Array-Größe	Selection Sort	Insertion Sort	Bubble Sort
100 Elemente	~0.1 ms	~0.05 ms	~0.15 ms
1,000 Elemente	~10 ms	~5 ms	~15 ms
10,000 Elemente	~1 Sekunde	~0.5 Sekunden	~1.5 Sekunden
100,000 Elemente	~100 Sekunden	~50 Sekunden	~150 Sekunden

⚠️ Merke: Bei großen Datenmengen sind O(n²)-Algorithmen zu langsam! Effizientere Algorithmen (O(n log n)) sortieren 100,000 Elemente in ~0.01 Sekunden!

Häufige Fehler beim Sortieren

❌ Fehler 1: Off-by-One

// FALSCH: i < n statt i < n-1
for (int i = 0; i < n; i++) {
    int minIdx = i;
    for (int j = i+1; j < n; j++)
        ...
}
                    

Letztes Element wird unnötig "sortiert"

❌ Fehler 2: Falscher Vergleich

// FALSCH: >= statt >
if (arr[j] >= arr[minIdx]) {
    minIdx = j;
}
                    

Macht stabilen Algorithmus instabil!

❌ Fehler 3: Swap vergessen

// FALSCH: nur einen Wert überschreiben
arr[i] = arr[minIdx];
// temp fehlt!
                    

Daten gehen verloren!

❌ Fehler 4: Falsche Grenzen

// Insertion Sort
for (int j = i; j >= 0; j--) {
    // FALSCH: j-1 kann -1 werden!
    if (arr[j] < arr[j-1])
}
                    

Array-Index out of bounds!

Vielen Dank!

Fragen zu Sortieralgorithmen?

Nächste Vorlesung: Binäre Suche & Komplexität

Wichtig für die Klausur

Alle drei Algorithmen verstehen und implementieren können
Wissen, welcher wann verwendet wird
Stabilität erkennen können
O-Notation verstehen