C/C++-Algorithmen

Bubble Sort

Jeder Durchlauf bewegt den größten unsortierten Wert ans Ende.

Was ist Bubble Sort?

Jeder Durchlauf bewegt den größten unsortierten Wert ans Ende.

Sortiere durch Tausch benachbarter Fehlordnungen.

Wichtige Punkte

Teste leere, einzelne, doppelte und sortierte Eingaben.
Trenne Korrektheit von Optimierung.
Nutze in Produktivcode bevorzugt die Standardbibliothek.

Bubble Sort visualisieren

O(n²)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Codebeispiele in C und C++

Code ausführen →

main.c

#include <stdio.h>

int main(void) {
    int values[] = {5, 1, 4, 2};
    for (int end = 3; end > 0; --end) {
        int changed = 0;
        for (int index = 0; index < end; ++index) {
            if (values[index] > values[index + 1]) {
                int temporary = values[index];
                values[index] = values[index + 1];
                values[index + 1] = temporary;
                changed = 1;
            }
        }
        if (!changed) break;
    }
    for (int index = 0; index < 4; ++index) {
        printf("%d ", values[index]);
    }
}

Erwartete Ausgabe

1 2 4 5

C++

Code ausführen →

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector values{5, 1, 4, 2};
    for (auto end = values.end(); end != values.begin(); --end) {
        bool changed = false;
        for (auto item = values.begin(); item + 1 != end; ++item) {
            if (*item > *(item + 1)) {
                std::iter_swap(item, item + 1);
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int value : values) {
        std::cout << value << ' ';
    }
}

Erwartete Ausgabe

1 2 4 5

Vergleich zwischen C und C++

Bubble Sort ist mit O(n²) vor allem lehrreich; früher Abbruch erreicht bei sortierter Eingabe O(n), in C++ nutzt man meist std::sort.

Schleifen, Pointer, Längen und Puffer sind explizit.

C++

Iteratoren und Algorithmen trennen Operation und Speicherung.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Verfolge jeden Vergleich manuell.
Teste Duplikate und Extremwerte.
Vergleiche die Laufzeit mit der Standardbibliothek.