BubbleSort

Quelle des Bildes

• Warum heißt das BubbleSort so?

Dieser Sortieralgorithmus heißt so, weil die größten Zahlen, wie in einer Blase nach oben aufsteigen. Aus diesem Grund wird dieser Algorithmus auch "Sortieren durch Aufsteigen" oder "Austauschsortieren" genannt.

• Prinzip

Bubblesort an einer Zahlenliste
In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Die Bubble-Phase wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. Auch werden immer zwei Zahlen miteinander in „Bubbles“ vertauscht.

Quelle des Bildes

• Java Code

public static int[] bubbleSort(int[] list) {
        int ready = 0; // anzahl der fertig sortierten Elemente
        boolean sorted = false;
        while (!sorted) {
            sorted = true;
            // new bubble / Bubble-Phase
            for (int i = 0; i < list.length - 1 - ready; i++) {
                if (list[i] > list[i + 1]) {
                    // swap list[i] and list [i + 1]
                    int zahl1 = list[i];
                    int zahl2 = list[i + 1];
                    list[i] = zahl2;
                    list[i + 1] = zahl1;
                    sorted = false;
                }
            }
            ready++;
        }
        return list;
}

• Beispiel an der Sortierung von Balken

Quelle des Bildes

• Verwendung

In der Praxis wird Bubblesort kaum eingesetzt, da andere Verfahren ein besseres Laufzeitverhalten haben. Der Algorithmus spielt allerdings in der Lehre eine Rolle, da er als einfach zu erklären bzw. zu demonstrieren gilt.