Labor 7: Sortieralgorithmen & Binäre Suche - Fortgeschrittene Programmierung

Zurück zur Startseite

Lernziele

In diesem Labor werden Sie:

Teil 1 - Sortieren: Bubble Sort und Selection Sort implementieren
Teil 2 - Suchen: Lineare und Binäre Suche implementieren
Teil 2 - Suchen: Komplexitaet O(n) vs O(log n) verstehen

Wichtige Konzepte

Bubble Sort: Nachbarelemente vergleichen und tauschen, O(n²)
Selection Sort: Minimum finden und an richtige Stelle setzen, O(n²)
Lineare Suche: Element für Element durchgehen, O(n)
Binäre Suche: Array halbieren (nur bei sortierten Arrays!), O(log n)
Voraussetzung: Binäre Suche funktioniert NUR bei sortierten Arrays!

Teil 1: Sortieralgorithmen (ca. 45 Min)

1 Bubble Sort implementieren

Aufgabenstellung

Implementieren Sie den Bubble Sort Algorithmus, um ein Array aufsteigend zu sortieren.

Bubble Sort - Die Idee

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

// Beispiel: [5, 3, 8, 1]

// Durchgang 1:
[5, 3, 8, 1] -> [3, 5, 8, 1]  // 5>3, tausche
[3, 5, 8, 1] -> [3, 5, 8, 1]  // 5<8, ok
[3, 5, 8, 1] -> [3, 5, 1, 8]  // 8>1, tausche

// Durchgang 2:
[3, 5, 1, 8] -> [3, 5, 1, 8]  // 3<5, ok
[3, 5, 1, 8] -> [3, 1, 5, 8]  // 5>1, tausche

// Durchgang 3:
[3, 1, 5, 8] -> [1, 3, 5, 8]  // 3>1, tausche

// Fertig: [1, 3, 5, 8]

Anforderungen

Erstellen Sie ein unsortiertes Array: {64, 34, 25, 12, 22, 11, 90}
Implementieren Sie Bubble Sort mit zwei verschachtelten Schleifen
Geben Sie das Array vor und nach dem Sortieren aus

Beispielausgabe

Unsortiert: 64 34 25 12 22 11 90
Sortiert:   11 12 22 25 34 64 90

Komplexität

Zeit: O(n²) - zwei verschachtelte Schleifen

Speicher: O(1) - nur eine temp-Variable für Swap

Musterlösung Falsches Passwort!

#include <stdio.h>

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

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Nach jedem Durchgang ist das größte Element am Ende
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Tausche
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

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

    printf("Unsortiert: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sortiert:   ");
    printArray(arr, n);

    return 0;
}

2 Selection Sort implementieren

Aufgabenstellung

Implementieren Sie den Selection Sort Algorithmus.

Selection Sort - Die Idee

Finde das Minimum im unsortierten Teil und tausche es an die richtige Position.

// Beispiel: [5, 3, 8, 1]

// Schritt 1: Finde Minimum (1), tausche mit arr[0]
[1, 3, 8, 5]  // Position 0 ist fertig

// Schritt 2: Finde Minimum in [3,8,5] = 3, schon richtig
[1, 3, 8, 5]  // Position 1 ist fertig

// Schritt 3: Finde Minimum in [8,5] = 5, tausche
[1, 3, 5, 8]  // Fertig!

Anforderungen

Verwenden Sie das gleiche Array wie in Aufgabe 1
Implementieren Sie Selection Sort
Zählen Sie die Anzahl der Vergleiche und Tausche

Beispielausgabe

Unsortiert: 64 34 25 12 22 11 90
Sortiert:   11 12 22 25 34 64 90
Vergleiche: 21
Tausche:    6

Musterlösung Falsches Passwort!

#include <stdio.h>

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

void selectionSort(int arr[], int n, int *vergleiche, int *tausche) {
    *vergleiche = 0;
    *tausche = 0;

    for (int i = 0; i < n - 1; i++) {
        // Finde Index des Minimums im unsortierten Teil
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            (*vergleiche)++;
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

        // Tausche nur wenn nötig
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
            (*tausche)++;
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = 7;
    int vergleiche, tausche;

    printf("Unsortiert: ");
    printArray(arr, n);

    selectionSort(arr, n, &vergleiche, &tausche);

    printf("Sortiert:   ");
    printArray(arr, n);
    printf("Vergleiche: %d\n", vergleiche);
    printf("Tausche:    %d\n", tausche);

    return 0;
}

3 Sortieralgorithmen vergleichen

Aufgabenstellung

Vergleichen Sie Bubble Sort und Selection Sort anhand der Anzahl der Operationen.

Anforderungen

Erstellen Sie ein Array mit 10 Zufallszahlen
Kopieren Sie das Array (beide Algorithmen sollen das gleiche Array sortieren)
Zählen Sie Vergleiche und Tausche für beide Algorithmen
Geben Sie die Ergebnisse in einer Tabelle aus

Beispielausgabe

Original: 42 17 89 3 55 12 77 23 8 61

Algorithmus      | Vergleiche | Tausche
-----------------|------------|--------
Bubble Sort      |     45     |   27
Selection Sort   |     45     |    9

Fazit: Selection Sort macht weniger Tausche!

Musterlösung Falsches Passwort!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

void copyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) dest[i] = src[i];
}

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

void selectionSort(int arr[], int n, int *vgl, int *swp) {
    *vgl = 0; *swp = 0;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            (*vgl)++;
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
            (*swp)++;
        }
    }
}

int main() {
    srand(time(NULL));
    int n = 10;
    int original[10], arr1[10], arr2[10];
    int vgl1, swp1, vgl2, swp2;

    // Zufallszahlen generieren
    for (int i = 0; i < n; i++) {
        original[i] = rand() % 100;
    }

    printf("Original: ");
    printArray(original, n);

    // Kopien erstellen
    copyArray(original, arr1, n);
    copyArray(original, arr2, n);

    // Sortieren
    bubbleSort(arr1, n, &vgl1, &swp1);
    selectionSort(arr2, n, &vgl2, &swp2);

    // Ergebnisse ausgeben
    printf("\nAlgorithmus      | Vergleiche | Tausche\n");
    printf("-----------------|------------|--------\n");
    printf("Bubble Sort      |     %2d     |   %2d\n", vgl1, swp1);
    printf("Selection Sort   |     %2d     |   %2d\n", vgl2, swp2);

    return 0;
}

Teil 2: Suchalgorithmen (ca. 45 Min)

4 Lineare Suche implementieren

Aufgabenstellung

Implementieren Sie die lineare Suche und zählen Sie die Vergleiche.

Lineare Suche - Die Idee

Gehe Element für Element durch, bis du das gesuchte findest (oder das Ende erreichst).

// Suche nach 8 in [3, 7, 2, 8, 5]
// Schritt 1: 3 == 8? Nein
// Schritt 2: 7 == 8? Nein
// Schritt 3: 2 == 8? Nein
// Schritt 4: 8 == 8? JA! -> Gefunden an Index 3

Anforderungen

Array: {15, 27, 3, 42, 8, 91, 56, 12, 77, 33}
Suchen Sie nach: 42, 33, und 100 (nicht vorhanden)
Geben Sie den Index und die Anzahl der Vergleiche aus

Beispielausgabe

Suche nach 42: Gefunden an Index 3 (4 Vergleiche)
Suche nach 33: Gefunden an Index 9 (10 Vergleiche)
Suche nach 100: Nicht gefunden (10 Vergleiche)

Musterlösung Falsches Passwort!

#include <stdio.h>

int linearSearch(int arr[], int n, int target, int *vergleiche) {
    *vergleiche = 0;
    for (int i = 0; i < n; i++) {
        (*vergleiche)++;
        if (arr[i] == target) {
            return i;  // Gefunden!
        }
    }
    return -1;  // Nicht gefunden
}

void sucheUndZeige(int arr[], int n, int target) {
    int vergleiche;
    int index = linearSearch(arr, n, target, &vergleiche);

    printf("Suche nach %d: ", target);
    if (index != -1) {
        printf("Gefunden an Index %d (%d Vergleiche)\n", index, vergleiche);
    } else {
        printf("Nicht gefunden (%d Vergleiche)\n", vergleiche);
    }
}

int main() {
    int arr[] = {15, 27, 3, 42, 8, 91, 56, 12, 77, 33};
    int n = 10;

    sucheUndZeige(arr, n, 42);
    sucheUndZeige(arr, n, 33);
    sucheUndZeige(arr, n, 100);

    return 0;
}

5 Binäre Suche implementieren

Aufgabenstellung

Implementieren Sie die binäre Suche für ein sortiertes Array.

Binäre Suche - Die Idee

Halbiere das Suchintervall in jedem Schritt. Funktioniert nur bei sortierten Arrays!

// Suche nach 23 in [5, 12, 17, 23, 38, 44, 77]
//                    0   1   2   3   4   5   6

// left=0, right=6, mid=3
// arr[3]=23 == 23? JA! Gefunden nach nur 1 Vergleich!

// Suche nach 44:
// left=0, right=6, mid=3: 23 < 44 -> suche rechts
// left=4, right=6, mid=5: 44 == 44? JA! (2 Vergleiche)

Wichtig!

Binäre Suche funktioniert NUR bei sortierten Arrays! Sortieren Sie das Array zuerst, falls nötig.

Anforderungen

Sortiertes Array: {3, 8, 12, 15, 27, 33, 42, 56, 77, 91}
Suchen Sie nach: 42, 33, und 100
Vergleichen Sie die Anzahl der Vergleiche mit linearer Suche

Beispielausgabe

Sortiertes Array: 3 8 12 15 27 33 42 56 77 91

Binäre Suche nach 42: Gefunden an Index 6 (4 Vergleiche)
Binäre Suche nach 33: Gefunden an Index 5 (3 Vergleiche)
Binäre Suche nach 100: Nicht gefunden (4 Vergleiche)

Vergleich mit linearer Suche:
- Linear: bis zu 10 Vergleiche
- Binär:  maximal 4 Vergleiche (log2(10) ≈ 3.3)

Komplexität im Vergleich

Algorithmus	Best Case	Worst Case	1000 Elemente
Lineare Suche	O(1)	O(n)	1000 Vergleiche
Binäre Suche	O(1)	O(log n)	~10 Vergleiche

Musterlösung Falsches Passwort!

#include <stdio.h>

int binarySearch(int arr[], int n, int target, int *vergleiche) {
    *vergleiche = 0;
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        (*vergleiche)++;
        int mid = left + (right - left) / 2;  // Vermeidet Overflow

        if (arr[mid] == target) {
            return mid;  // Gefunden!
        } else if (arr[mid] < target) {
            left = mid + 1;  // Suche rechts
        } else {
            right = mid - 1;  // Suche links
        }
    }

    return -1;  // Nicht gefunden
}

void sucheUndZeige(int arr[], int n, int target) {
    int vergleiche;
    int index = binarySearch(arr, n, target, &vergleiche);

    printf("Binäre Suche nach %d: ", target);
    if (index != -1) {
        printf("Gefunden an Index %d (%d Vergleiche)\n", index, vergleiche);
    } else {
        printf("Nicht gefunden (%d Vergleiche)\n", vergleiche);
    }
}

int main() {
    // WICHTIG: Array muss sortiert sein!
    int arr[] = {3, 8, 12, 15, 27, 33, 42, 56, 77, 91};
    int n = 10;

    printf("Sortiertes Array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n\n");

    sucheUndZeige(arr, n, 42);
    sucheUndZeige(arr, n, 33);
    sucheUndZeige(arr, n, 100);

    printf("\nVergleich mit linearer Suche:\n");
    printf("- Linear: bis zu %d Vergleiche\n", n);
    printf("- Binär:  maximal ~4 Vergleiche (log2(%d))\n", n);

    return 0;
}

6 Sortieren und Suchen kombinieren

Aufgabenstellung

Schreiben Sie ein Programm, das ein unsortiertes Array sortiert und dann binär durchsucht.

Anforderungen

Unsortiertes Array: {72, 11, 45, 3, 88, 29, 67, 5, 99, 14}
Sortieren Sie das Array mit Selection Sort oder Bubble Sort
Suchen Sie dann mit binärer Suche nach: 45, 88, und 50
Zeigen Sie den Unterschied in der Effizienz

Beispielausgabe

Unsortiert: 72 11 45 3 88 29 67 5 99 14
Sortiert:   3 5 11 14 29 45 67 72 88 99

Binäre Suche nach 45: Gefunden! Index 5 (3 Vergleiche)
Binäre Suche nach 88: Gefunden! Index 8 (4 Vergleiche)
Binäre Suche nach 50: Nicht gefunden (4 Vergleiche)

Musterlösung Falsches Passwort!

#include <stdio.h>

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

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

int binarySearch(int arr[], int n, int target, int *vergleiche) {
    *vergleiche = 0;
    int left = 0, right = n - 1;

    while (left <= right) {
        (*vergleiche)++;
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

void sucheUndZeige(int arr[], int n, int target) {
    int vergleiche;
    int index = binarySearch(arr, n, target, &vergleiche);

    printf("Binäre Suche nach %d: ", target);
    if (index != -1) {
        printf("Gefunden! Index %d (%d Vergleiche)\n", index, vergleiche);
    } else {
        printf("Nicht gefunden (%d Vergleiche)\n", vergleiche);
    }
}

int main() {
    int arr[] = {72, 11, 45, 3, 88, 29, 67, 5, 99, 14};
    int n = 10;

    printf("Unsortiert: ");
    printArray(arr, n);

    // Erst sortieren
    selectionSort(arr, n);

    printf("Sortiert:   ");
    printArray(arr, n);
    printf("\n");

    // Dann binär suchen
    sucheUndZeige(arr, n, 45);
    sucheUndZeige(arr, n, 88);
    sucheUndZeige(arr, n, 50);

    return 0;
}

Zusammenfassung

Algorithmus	Komplexität	Besonderheit
Bubble Sort	O(n²)	Einfach zu verstehen, viele Tausche
Selection Sort	O(n²)	Weniger Tausche als Bubble Sort
Lineare Suche	O(n)	Funktioniert immer, langsam bei großen Arrays
Binäre Suche	O(log n)	Sehr schnell, aber Array muss sortiert sein!