Bubble Sort

Du kennst es wahrscheinlich: Schüttest Du z. B. Sprudelwasser in ein Glas, kannst Du beobachten, wie die Bläschen nach oben steigen. Dieses Phänomen findet sich nicht nur bei Getränken mit Kohlensäure, sondern auch bei den Sortieralgorithmen. Klingt etwas abgedreht – ist es aber gar nicht. Tatsächlich ist der Bubble Sort Algorithmus genau wegen dieses Prinzips erst zu seinem Namen gekommen.

Bubble Sort Erklärung

Jetzt stellt sich natürlich die Frage, was Bubble Sort überhaupt ist. Die grundlegende Idee hinter dem Sortieralgorithmus ist es, benachbarte Elemente miteinander zu vergleichen und zu vertauschen, wenn sie nicht die richtige Reihenfolge haben.

Bubble Sort Definition

Durch dieses Prinzip steigen Elemente quasi wie Blasen (engl. "bubble") durch das zu sortierende Array auf – wodurch der Algorithmus seinen Namen bekommen hat.

Bubble Sort Algorithmus

Beim Bubblesort Algorithmus wird eine Datenmenge von links nach rechts durchlaufen. Zwei nebeneinander liegende Elemente werden bezüglich des Tauschkriteriums miteinander verglichen und getauscht, wenn nötig. Das wird so lange weitergeführt, bis es keine Vertauschungen mehr gibt.

Wie Bubblesort in der Praxis funktioniert, lässt sich am besten an einem einfachen Beispiel zeigen. Gegeben ist das Array [5, 2, 8, 4, 9, 7]:

Bubble Sort Vorgehensweise

Nachdem Du ein Beispiel gesehen hast, hier noch einmal zusammengefasst, wie der Bubblesort Algorithmus abläuft:

• Kriterium für die Sortierung festlegen
• Datenmenge vollständig durchgehen
• Zwei aufeinanderfolgende Elemente vertauschen, wenn die Reihenfolge nicht stimmt
• Solange fortfahren, bis keine Vertauschungen mehr notwendig sind

Bubble Sort Komplexität

Jetzt, wo Du weißt, wie Bubble Sort grundsätzlich funktioniert, stellt sich die Frage, wie es eigentlich mit der Komplexität aussieht?

Bubble Sort Laufzeit

Bei der Laufzeit des Bubble Sorts müssen der Best-Case, Average-Case und der Worst-Case voneinander unterschieden werden.

Best-Case

Besonders effizient ist Bubblesort bei bereits vorsortierten Datenmengen, da dort der Algorithmus nur einmal durchgegangen und keine Vertauschungen vorgenommen werden müssen.

Worst-Case

Der schlechteste Fall liegt vor, wenn die Datenmenge zu Beginn absteigend sortiert ist. Das liegt daran, dass dann im Grunde alle Elemente von links nach rechts verschoben werden müssen und somit viele Vertauschungen benötigt werden, bis die Datenmenge vollständig sortiert ist.

Average-Case

Die durchschnittliche Laufzeit beim Bubblesort ist hingegen nicht ganz so leicht zu ermitteln – zumindest nicht ohne mathematischen Beweis. Was Du Dir jedoch merken kannst: Der Average-Case hat ungefähr die Hälfte der Tauschoperationen des Worst-Case. Das heißt, auch hier würde die Laufzeit O(n²) betragen.

Bubble Sort Platzkomplexität

Der Bubblesort Algorithmus arbeitet in-place. Außerdem besitzt er eine Platzkomplexität von O(1) – also einen konstanten zusätzlichen Speicheraufwand.

Bubble Sort – Weitere Begrifflichkeiten

Weitere wichtige Begriffe, die Du im Rahmen des Bubble Sort Algorithmus schon einmal gehört haben solltest, werden in den folgenden Abschnitten erläutert. Dazu gehören:

• Stabilität
• Vergleichsbasiert
• Iterativ vs. rekursiv
• Parallelisierbarkeit

Bubble Sort Stabilität

Beim Bubble Sort handelt es sich um einen stabilen Sortieralgorithmus. Das liegt daran, dass gleiche benachbarte Elemente nicht miteinander vertauscht werden und ihre ursprüngliche Reihenfolge somit nicht verändert wird.

Bubble Sort vergleichsbasiert

Bubblesort arbeitet vergleichsbasiert, da immer zwei Elemente einer Datenmenge miteinander verglichen werden.

Bubble Sort iterativ – rekursiv

Bubble Sort kann sowohl iterativ als auch rekursiv implementiert werden.

Bubble Sort Parallelisierbarkeit

Um den Bubblesort zu parallelisieren, gibt es zwei unterschiedliche Möglichkeiten:

• Odd-even Sort
• Divide and Conquer

Odd-even Sort

Beim Odd-even Sort werden gleichzeitig jeweils benachbarte Elemente miteinander verglichen und vertauscht, wenn die Reihenfolge nicht stimmt – also das Erste und Zweite, das Dritte und Vierte usw.. Bei der nächsten Iteration werden dann das zweite und dritte, vierte und fünfte usw. Element miteinander verglichen. Die beiden Schritte werden abwechselnd so lange fortgeführt, bis das Array vollständig sortiert ist.

Divide and Conquer

Beim Divide and Conquer wird das zu sortierende Element in mehrere Bereiche eingeteilt, die dann mit dem Bubblesort parallel durchlaufen und sortiert werden. Sind die einzelnen Unterteilungen alle fertig, wird das letzte Element aus einem Bereich mit dem ersten Element aus dem nächsten Bereich verglichen. Danach beginnt das Ganze wieder von vorne und läuft so lange, bis keine Vertauschungen mehr zu finden sind.

Bubble Sort Zusammenfassung

In der folgenden Übersicht findest Du alles bisher gelernte zum Bubblesort noch einmal auf einen Blick:

Bubble Sort Problem

Eines der Hauptprobleme des Bubblesort ist seine Effizienz, bzw. die Laufzeit. Große Elemente werden zunächst relativ schnell richtig am Ende einer Liste einsortiert. Kleinere Elemente werden jedoch nur eher langsam nach vorn verschoben.

Wie kannst Du das Problem lösen? Dazu gibt es theoretisch zwei Ansätze:

• Shaker Sort
• Combsort

Shaker Sort

Bei beiden Lösungsansätze handelt es sich im Grunde um modifizierte Bubblesort Algorithmen. Der Shaker Sort – auch Cocktail Sort oder BiDiBubble Sort genannt – hat zwar ebenfalls eine Laufzeit von O(n²), allerdings durchläuft er eine Liste abwechselnd von oben und von unten. Dadurch werden abwechselnd immer die kleinsten Elemente nach links und die größten nach rechts einsortiert, was das oben genannte Problem des Bubblesort verbessert.

Combsort

Der zweite Ansatz ist der sogenannte Combsort. Dieser Algorithmus beginnt damit, weit auseinanderliegende Elemente miteinander nach einem gap Index zu vergleichen. Dieser Index wird nach jedem Durchlauf um den Faktor 1,3 reduziert. Der Algorithmus ist beendet, wenn gap = 1, da er ab dem Punkt im Grunde identisch mit dem Bubble Sort ist.

Im Worst-Case und Average-Case hat der Combsort ebenfalls eine Komplexität von O(n²), im Best-Case beträgt die Laufzeit allerdings O(n log n) und ist somit eine Verbesserung des eigentlichen Bubblesort.

Bubble Sort Beispiel

Um den Bubblesort für Dich noch etwas anschaulicher zu machen, folgen nun noch ein paar konkrete (Code-)Beispiele.

Bubble Sort Anwendung

Wann wird Bubblesort hauptsächlich verwendet?

• Wenn die Komplexität keine große Rolle spielt
• Wenn einfacher Code benötigt wird

Pseudocode

Jetzt fragst Du Dich vielleicht, wie man den Bubblesort implementieren würde. In Pseudocode wäre z. B. folgende Schreibweise denkbar:

bubblesort (Array A)
var n = integer
begin
        repeat
                for n := 1 to (N − 1) do
                        if A[n].key > A[n + 1].key
                then {vertausche A[n] und A[n + 1]}
        until {keine Vertauschung mehr nötig}
end

Gegeben ist ein Array – hier A genannt – und ein Integerwert (n). Eine Schleife geht dann durch das gegebene Array durch und schaut bei zwei nebeneinanderliegenden Werten, ob der erste (n) größter ist als der zweite (n + 1). Wenn das der Fall ist, werden die Werte vertauscht. Das Ganze läuft so lange, bis keine Vertauschungen mehr auftreten. Dann endet der Algorithmus.

Bubble Sort Java

Eine mögliche Implementation vom Bubble Sort in Java, könnte wie folgt aussehen:

import java.util.Arrays; 

class Main {
// Hilfsfunktion für das Vertauschen von Elementen im Array
// temp = Hilfsvariable

    public static void swap(int[] array, int n, int m) {
        int temp = array[n];
        array[n] = array[m];
        array[m] = temp;
    }

    // Funktion zum Durchführen von Bubble Sort für ein gegebenes Array

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {

            // Die letzten Elemente sind bereits sortiert, die innere Schleife kann also beendet werden

            for (int j = 0; j < array.length - 1 - j; j++) {
                    if (array[j] > array[j + 1]) {
                            swap(array, j, j + 1);
                            }
                    }

// Der Algorithmus kann beendet werden, wenn die innere Schleife keine Vertauschungen mehr durchführt

        }
    }

    public static void main(String[] args) {
         int[] array = { 5, 2, 8, 4, 9, 7 };
    bubbleSort(array);

        // sortiertes Array ausgeben lassen

        System.out.println(Arrays.toString(array));
    }
}

Als Ausgabe erhältst Du dann folgendes Ergebnis:

[2, 4, 5, 7, 8, 9]