Der Bubble-Sort-Algorithmus

Eine Liste zu sortieren ist eines der ersten Probleme, die jeder Programmierer löst, und Bubble Sort ist meist der erste Algorithmus dafür. Er ist nicht schnell und außerhalb des Klassenzimmers selten die richtige Wahl — aber er ist kurz, braucht keinen zusätzlichen Speicher, und sein Verhalten lässt sich Schritt für Schritt gut beobachten, was ihn zu einem guten Einstieg macht, bevor man sich schnellere Algorithmen wie Quicksort oder Merge Sort ansieht.

Die Idee

Bubble Sort durchläuft die Liste wiederholt und vergleicht jedes Paar benachbarter Elemente. Ist ein Paar falsch angeordnet, werden die beiden vertauscht. Ein vollständiger Durchlauf befördert den größten verbleibenden Wert bis ganz ans Ende der Liste — wie eine Blase, die aufsteigt — denn jeder Tausch, der ihn betrifft, trägt ihn eine Position weiter nach rechts.

Nach dem ersten Durchlauf steht fest, dass das größte Element an seiner finalen Position ist, sodass der nächste Durchlauf nur noch alles davor betrachten muss. Das für n - 1 Durchläufe über eine Liste mit n Elementen zu wiederholen reicht aus, um sie vollständig zu sortieren, da jeder Durchlauf mindestens ein weiteres Element endgültig platziert.

Implementierung

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
int i = 0;
int j = 0;
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int k = 0; k < N; k++) {
        values[k] = k + 1;
    }

    srand(1);
    for (int k = N - 1; k > 0; k--) {
        int r = rand() % (k + 1);
        int tmp = values[k];
        values[k] = values[r];
        values[r] = tmp;
    }
}

void frame() {
    // Slow the animation down: one comparison every few frames instead of
    // one per frame, so individual steps stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (values[j] > values[j + 1]) {
            int tmp = values[j];
            values[j] = values[j + 1];
            values[j + 1] = tmp;
        }

        j++;
        if (j >= N - 1 - i) {
            j = 0;
            i++;
            if (i >= N - 1) {
                done = true;
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int k = 0; k < N; k++) {
        if (!done && (k == j || k == j + 1)) {
            PlotColor(220, 60, 60);   // pair being compared
        } else if (k >= N - i) {
            PlotColor(70, 170, 90);   // already in final position
        } else {
            PlotColor(30, 100, 200);  // untouched
        }

        int height = values[k] * (plot_height - 20) / N;
        int x0 = k * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

Die beiden verschachtelten Schleifen spiegeln die beiden Ideen von oben: der äußere Index i zählt, wie viele Elemente am Ende der Liste bereits endgültig platziert sind, und der innere Index j läuft durch den noch unsortierten Teil und vergleicht Nachbarn. Statt etwas auszugeben, zeichnet frame() das Array als Balken — die Höhe ist der Wert, die Farbe zeigt, was der Algorithmus gerade tut:

• blau — unberührt, noch unsortiert
• rot — das Paar, das gerade verglichen wird
• grün — bereits an seiner finalen Position

Damit einzelne Vergleiche sichtbar bleiben statt sofort durchzulaufen, führt das Sample nur alle paar Aufrufe von frame() einen Vergleich aus (siehe den tick-Zähler) — alles andere, einschließlich des Mischens des Arrays in setup(), läuft genau einmal.

Schritt für Schritt durchgerechnet

Für die Liste [5, 1, 4, 2, 8] vergleicht der erste Durchlauf jedes benachbarte Paar von links nach rechts:

8 — der größte Wert — ist nach nur einem Durchlauf an seine finale Position geblubbert. Die restlichen Durchläufe wiederholen denselben Prozess über das schrumpfende unsortierte Präfix [1, 4, 2, 5], [1, 2, 4] und so weiter, bis nichts mehr zu vergleichen bleibt.

Warum er selten verwendet wird

Jeder Durchlauf kostet O(n), und eine vollständige Sortierung braucht bis zu n - 1 Durchläufe, also ist Bubble Sort im schlechtesten und im durchschnittlichen Fall O(n²) — quadratisch schlechter als das O(n log n) von Merge Sort oder Quicksort. Eine gängige Optimierung merkt sich, ob während eines Durchlaufs überhaupt getauscht wurde, und bricht frühzeitig ab, falls nicht — das drückt den besten Fall (eine bereits sortierte Liste) auf O(n). Die Version hier verzichtet auf diese Prüfung, um Code und Visualisierung einfach zu halten; jeder Lauf macht unabhängig von der Eingabe alle n - 1 Durchläufe.

Sein heutiger Wert ist fast ausschließlich pädagogisch: Er ist die einfachste mögliche Einführung in vergleichsbasiertes Sortieren und eine nützliche Grundlinie, um schnellere Algorithmen zu vergleichen, die dasselbe Problem mit klügeren Strategien lösen — die Liste zu teilen statt sie wiederholt zu durchlaufen, wie bei Merge Sort und Quicksort.

Fazit

Bubble Sort verwandelt Sortieren in eine Folge lokaler Entscheidungen: zwei Nachbarn ansehen, sie vertauschen, falls sie falsch herum stehen, und das wiederholen, bis nichts mehr zu korrigieren ist. Diese Einfachheit macht ihn zu einer schlechten Wahl für große Listen, aber zu einer guten, um ein Gefühl dafür zu entwickeln, was ein Sortieralgorithmus tatsächlich tut — einen Vergleich nach dem anderen.