Labor 7: Sortieren & Array-Manipulation - Grundlagen der Programmierung

Zur Startseite

Lernziele

In diesem Labor werden Sie:

Teil 1 - Sortieren: Bubble Sort implementieren
Teil 2 - Array-Manipulation: Arrays umkehren und verschieben

Wichtige Konzepte

Bubble Sort: Nachbarelemente vergleichen und tauschen
Array umkehren: Erstes mit letztem Element tauschen, usw.
Array verschieben: Elemente rotieren (links/rechts)
Palindrom: Von beiden Enden vergleichen

Teil 1: Sortieren mit Bubble Sort (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 noetig 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

Musterloesung 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 groesste 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 Bubble Sort analysieren

Aufgabenstellung

Erweitern Sie Bubble Sort, um die Anzahl der Vergleiche und Tausche zu zaehlen.

Anforderungen

Verwenden Sie das gleiche Array wie in Aufgabe 4
Zaehlen Sie, wie oft verglichen wird
Zaehlen Sie, wie oft getauscht wird
Geben Sie beide Werte aus

Beispielausgabe

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

Vergleiche: 21
Tausche:    12

Musterloesung Falsches Passwort!

#include <stdio.h>

// Globale Variablen zum Zaehlen
int vergleiche = 0;
int tausche = 0;

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++) {
        for (int j = 0; j < n - 1 - i; j++) {
            vergleiche++;  // Jeder Vergleich wird gezaehlt
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                tausche++;  // Nur wenn getauscht wird
            }
        }
    }
}

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);

    printf("\nVergleiche: %d\n", vergleiche);
    printf("Tausche:    %d\n", tausche);

    return 0;
}

Teil 2: Array-Manipulation (ca. 45 Min)

3 Array umkehren (Reverse)

Aufgabenstellung

Kehren Sie die Reihenfolge der Elemente in einem Array um.

Reverse - Die Idee

Tausche das erste Element mit dem letzten, das zweite mit dem vorletzten, usw.

// Array: [1, 2, 3, 4, 5]
// Index:  0  1  2  3  4

// Schritt 1: Tausche arr[0] mit arr[4]
// [5, 2, 3, 4, 1]

// Schritt 2: Tausche arr[1] mit arr[3]
// [5, 4, 3, 2, 1]

// Fertig! (Mitte muss nicht getauscht werden)

Anforderungen

Array: {1, 2, 3, 4, 5, 6, 7}
Kehren Sie das Array um (in-place, ohne zweites Array)
Geben Sie das Array vor und nach dem Umkehren aus

Beispielausgabe

Vorher:  1 2 3 4 5 6 7
Nachher: 7 6 5 4 3 2 1

Musterloesung 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 reverseArray(int arr[], int n) {
    int left = 0;
    int right = n - 1;

    while (left < right) {
        // Tausche links und rechts
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        // Indizes aufeinander zubewegen
        left++;
        right--;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = 7;

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

    reverseArray(arr, n);

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

    return 0;
}

4 Array nach links verschieben

Aufgabenstellung

Verschieben Sie alle Elemente um eine Position nach links. Das erste Element kommt ans Ende.

Links-Shift - Die Idee

// Array: [1, 2, 3, 4, 5]

// 1. Erstes Element merken: temp = 1
// 2. Alle Elemente eins nach links: [2, 3, 4, 5, 5]
// 3. temp ans Ende: [2, 3, 4, 5, 1]

Anforderungen

Array: {10, 20, 30, 40, 50}
Verschieben Sie einmal nach links
Geben Sie das Array vor und nach dem Verschieben aus

Beispielausgabe

Vorher:  10 20 30 40 50
Nachher: 20 30 40 50 10

Musterloesung Falsches Passwort!

#include <stdio.h>

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

// Einmal nach links verschieben
void shiftLeft(int arr[], int n) {
    int temp = arr[0];  // Erstes Element merken

    for (int i = 0; i < n - 1; i++) {
        arr[i] = arr[i + 1];  // Nach links schieben
    }

    arr[n - 1] = temp;  // Erstes Element ans Ende
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = 5;

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

    shiftLeft(arr, n);

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

    return 0;
}

5 Palindrom pruefen

Aufgabenstellung

Pruefen Sie, ob ein Array ein Palindrom ist (vorwaerts und rueckwaerts gleich).

Palindrom-Pruefung

Ein Palindrom liest sich vorwaerts und rueckwaerts gleich.

// Beispiele:
// [1, 2, 3, 2, 1] -> Palindrom!
// [1, 2, 3, 4, 5] -> Kein Palindrom

// Idee: Vergleiche arr[0] mit arr[n-1], arr[1] mit arr[n-2], usw.

Anforderungen

Testen Sie: {1, 2, 3, 2, 1} und {1, 2, 3, 4, 5}
Geben Sie aus, ob das Array ein Palindrom ist

Beispielausgabe

Array 1: 1 2 3 2 1
-> Ist ein Palindrom!

Array 2: 1 2 3 4 5
-> Ist KEIN Palindrom!

Musterloesung Falsches Passwort!

#include <stdio.h>

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

int istPalindrom(int arr[], int n) {
    int left = 0;
    int right = n - 1;

    while (left < right) {
        if (arr[left] != arr[right]) {
            return 0;  // Kein Palindrom
        }
        left++;
        right--;
    }

    return 1;  // Ist Palindrom
}

int main() {
    int arr1[] = {1, 2, 3, 2, 1};
    int n1 = 5;

    int arr2[] = {1, 2, 3, 4, 5};
    int n2 = 5;

    printf("Array 1: ");
    printArray(arr1, n1);
    if (istPalindrom(arr1, n1)) {
        printf("-> Ist ein Palindrom!\n\n");
    } else {
        printf("-> Ist KEIN Palindrom!\n\n");
    }

    printf("Array 2: ");
    printArray(arr2, n2);
    if (istPalindrom(arr2, n2)) {
        printf("-> Ist ein Palindrom!\n");
    } else {
        printf("-> Ist KEIN Palindrom!\n");
    }

    return 0;
}

Zusammenfassung

Thema	Wichtige Funktionen/Konzepte
Bubble Sort	Nachbarelemente vergleichen und tauschen
Array Reverse	Erstes mit letztem tauschen (von beiden Seiten)
Array Shift	Erstes merken, alle verschieben, ans Ende setzen
Palindrom	Von beiden Enden vergleichen