|
|
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. 

Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

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 gibt es übrigens schon ein Weilchen – erste Erwähnungen stammen aus den 1950er-Jahren. Vermutlich wurde das Prinzip des Algorithmus aber auch schon davor angewendet.

Bubble Sort Definition

Bubble Sort ist ein Sortieralgorithmus, bei dem nebeneinanderliegende Elemente miteinander verglichen werden. Liegt nicht die gewünschte Reihenfolge vor, werden die Elemente getauscht.

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

Falls Du Dich wunderst, ob es Bubble Sort oder Bubblesort heißt – beide Schreibweisen sind korrekt!

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.

Spätestens nach dem ersten Durchlauf sollte das größte Element ganz rechts platziert sein! Spätestens deshalb, weil es natürlich auch sein kann, dass das größte Element schon von Beginn an ganz rechts liegt.

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]:

IterationenDurchführungUnsortiertSortiert
Schritt 1Teile das Array zunächst in einen unsortierten (links) und einen sortierten (rechts) Bereich ein. Vergleiche dann die ersten beiden Elemente miteinander, also die 5 und die 2. Die 2 ist in diesem Fall kleiner, also vertausche die beiden Elemente. 528497
Vergleiche nun das zweite und das dritte Element. Die 5 und die 8 sind bereits in der richtigen Reihenfolge. 258497
Die 8 und die 4 müssen wieder vertauscht werden.254897
Die 8 und die 9 sind in der richtigen Reihenfolge, die 9 und die 7 müssen jedoch noch vertauscht werden. Danach bist Du am Ende der 1. Iteration. Die 9 ist an dieser Stelle theoretisch schon richtig einsortiert.254879
Schritt 2Der nächste Schritt beginnt wieder am Anfang des Arrays, die 2 und die 5 haben bereits die richtige Reihenfolge.254879
Die 5 und die 4 müssen miteinander vertauscht werden.245879
Die 5 und die 8 befinden sich in der korrekten Reihenfolge, die 8 und die 7 müssen jedoch vertauscht werden, dann hast Du das Ende der 2. Iteration erreicht. 245789
Schritt 3Gehe das Array erneut Schritt für Schritt durch. Bei den einzelnen Vergleichen wirst Du feststellen, dass im Array keine Vertauschungen mehr nötig sind – der Algorithmus ist somit beendet.245789

Anmerkung: Im Beispiel wird eine Weiterentwicklung des Bubblesort gezeigt. Im ursprünglichen Algorithmus wird bei jeder Iteration das gesamte Array durchlaufen. In der überarbeiteten Variante wird eine Grenze eingeführt, die den sortierten vom unsortierten Bereich trennt.

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.

Der Best-Case hat dementsprechend eine Laufzeit von O(n).

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.

Die Laufzeit im Worst-Case beträgt also O(n2).

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(n2) betragen.

Falls Du die Laufzeiten selbst mal testest, könnte Dir auffallen, dass Bubble Sort bei absteigend sortierten Datenmengen trotzdem noch schneller ist als bei zufällig angeordneten Datenmengen. Doch woran liegt das?

Das Phänomen lässt sich durch die "branch prediction" (Sprungvorhersage) erklären. Bei einer absteigend sortierten Datenmenge kann davon ausgegangen werden, dass ein Vergleich zwischen zwei Elementen immer false ist und die Elemente somit vertauscht werden müssen. Bei einer zufälligen Datenmenge kann man nicht genau sagen, ob der Vergleich true oder false sein wird.

Das sorgt letztlich dafür, dass die Befehls-Pipeline der CPU bei einer absteigend sortierten Datenmenge voll ausgenutzt werden kann. Bei einer zufälligen Vorsortierung muss die Pipeline häufiger gelöscht und neu befüllt werden – das Ganze dauert also länger!

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

Beide Möglichkeiten machen den Bubblesort Algorithmus übrigens auch schneller.

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.

Die Anzahl der Bereiche hängt davon ab, wie viele Kerne (Cores) Dein Prozessor besitzt.

Bubble Sort Zusammenfassung

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

Best-CaseAverage-CaseWorst-CasePlatz-komplexitätStabiles Verfahrenvergleichs-basiertIn-PlaceParallelisier-barkeititerativ/rekursiv
O(n)O(n2)O(n2)O(1)JaJaJaMöglichBeides

Bubble Sort Vorteile – Nachteile

Hier findest Du die Vor- und Nachteile des Bubblesort tabellarisch zusammengefasst:

VorteileNachteile
Einfacher, simpler CodeIst nur bei vorsortierten Mengen effizient

Grundsätzlich eignet sich der Bubble Sort Algorithmus vor allem für Anfänger, da er leicht zu verstehen und vergleichsweise einfach zu implementieren ist.

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(n2), 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.

Der Faktor 1,3 ist ein empirisch entwickelter Wert, der die Bildung von Clustern in Datenmengen verhindern soll.

Im Worst-Case und Average-Case hat der Combsort ebenfalls eine Komplexität von O(n2), 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]

Bubble Sort – Das Wichtigste

  • Bubble Sort Definition: Der Bubble Sort ist ein Sortieralgorithmus, bei dem nebeneinanderliegende Elemente miteinander verglichen werden. Liegt nicht die gewünschte Reihenfolge vor, werden die Elemente vertauscht.
  • Die Laufzeit vom Bubble Sort beträgt im Worst-Case und Average-Case O(n2) und im Best-Case O(n).
  • Die Platzkomplexität beträgt O(1).
  • Bubble Sort Stabilität: Es handelt sich um einen einfachen, stabilen Algorithmus, der vergleichsbasiert arbeitet.
  • Der Bubble Sort ist durch zwei Möglichkeiten parallelisierbar:
    • Odd-even Sort

    • Divide and Conquer

  • Bubble Sort Problem: Große Elemente werden schnell am Ende einer Liste einsortiert. Kleinere Elemente werden jedoch nur eher langsam nach vorn verschoben.
    • Lösungsansätze dafür sich der Shaker Sort oder der Combsort.
  • Bubble Sort Beispiel: Der Algorithmus wird vor allem verwendet, wenn die Komplexität keine große Rolle spielt und wenn einfacher Code benötigt wird.


Nachweise

  1. Thomas Ottmann; Peter Widmayer (2012). Algorithmen und Datenstrukturen. Spektrum.
  2. Happycoders.eu: Bubble Sort – Algorithmus, Quellcode, Zeitkomplexität. (26.10.2022)

Häufig gestellte Fragen zum Thema Bubble Sort

Beim Bubble Sort werden zwei benachbarte Elemente miteinander verglichen und vertauscht, wenn sie nicht der richtigen Reihenfolge entsprechen. 

Beim Bubble Sort handelt es sich um einen stabilen Sortieralgorithmus, da gleiche benachbarte Elemente nicht vertauscht werden. 

Beim Bubble Sort handelt es sich um einen einfachen, stabilen, vergleichsbasierten Sortieralgorithmus. 

Der Bubble Sort hat nicht den "Einen" Erfinder. Der Sortieralgorithmus wird in den 1950er-Jahren jedoch das erste Mal erwähnt.

Teste dein Wissen mit Multiple-Choice-Karteikarten

Wahr oder falschBeim Bubble Sort handelt es sich um einen vergleichsbasierten Sortieralgorithmus.

Wahr oder falschDie Komplexität beträgt beim Bubblesort im Best-Case O(n2).

Wahr oder falschDie Komplexität beträgt beim Bubblesort im Worst-Case O(n2).

Weiter

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Melde dich an für Notizen & Bearbeitung. 100% for free.

Entdecke Lernmaterial in der StudySmarter-App

Google Popup

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!