Deutsche Lernausgabe

Bubblesort in C

Tauschen Sie falsch geordnete Nachbarn und beobachten Sie, wie das Maximum ans Ende wandert.

Vergleichen Sie in jedem Durchlauf benachbarte Elemente und tauschen Sie sie bei Bedarf. Das größte Element des verbleibenden Bereichs gelangt ans Ende; der nächste Durchlauf kann daher kürzer sein.

Eine Markierung erlaubt den Abbruch, wenn nichts getauscht wurde. Damit kostet eine bereits sortierte Eingabe O(N), allgemeiner und schlechtester Fall bleiben aber O(N²). Der Hilfsspeicher beträgt O(1).

Greifen Sie nicht auf arr[j + 1] zu, wenn j bereits der letzte Index ist. Testen Sie Duplikate und umgekehrte Reihenfolgen. Tauschen nur bei strikt größerem linken Wert erhält die Reihenfolge gleicher Werte.

Quellcode

#include <stdio.h>
#include <stdbool.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // Array is already sorted
    }
}

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

int main(void) {
    int data[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(data) / sizeof(data[0]);

    printf("Original array: ");
    print_array(data, n);

    bubble_sort(data, n);

    printf("Sorted array:   ");
    print_array(data, n);
    return 0;
}

Im Compiler öffnen

Erwartetes Ergebnis

Original array: 64 34 25 12 22 11 90 
Sorted array:   11 12 22 25 34 64 90

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.