Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|
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. Jetzt…

Von Expert*innen geprüfte Inhalte
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 200 Millionen kostenlose Materialien in unserer App

Bubble Sort

Speicher die Erklärung jetzt ab und lies sie, wenn Du Zeit hast.

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

Finales Bubble Sort Quiz

Bubble Sort Quiz - Teste dein Wissen

Frage

Wahr oder falsch

Beim Bubble Sort handelt es sich um einen vergleichsbasierten Sortieralgorithmus.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Definiere den Bubble Sort Sortieralgorithmus.

Antwort anzeigen

Antwort

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

Frage anzeigen

Frage

Woher hat der Bubble Sort Algorithmus seinen Namen?

Antwort anzeigen

Antwort

Der Bubble Sort heißt so, weil Elemente beim Sortieren wie Blasen (bubble) aufsteigen. 

Frage anzeigen

Frage

Bringe die folgende Vorgehensweise in die richtige Reihenfolge:

(1) Datenmenge vollständig durchgehen

(3) Kriterium für die Sortierung festlegen

(4) Zwei aufeinanderfolgende Elemente vertauschen, wenn die Reihenfolge nicht stimmt

 (2) Solange fortfahren, bis keine Vertauschungen mehr notwendig sind

Antwort anzeigen

Antwort

3, 1, 4, 2

Frage anzeigen

Frage

Wahr oder falsch

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

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Wahr oder falsch

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

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Der Bubble Sort Algorithmus arbeitet ______ (1) und besitzt eine ______ (2) von O(1).

Antwort anzeigen

Antwort

(1) in-place

(2) Platzkomplexität   

Frage anzeigen

Frage

Wahr oder falsch

Der Bubblesort ist ein instabiler Sortieralgorithmus.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Warum ist der Bubble Sort nicht instabil?

Antwort anzeigen

Antwort

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

Frage anzeigen

Frage

Nenne zwei Möglichkeiten, um den Bubblesort zu parallelisieren.

Antwort anzeigen

Antwort

  • Odd-even Sort
  • Divide and Conquer

Frage anzeigen

Frage

Welche Lösungsansätze gibt es für das Hauptproblem des Bubble Sorts?

Antwort anzeigen

Antwort

  • Shaker Sort
  • Combsort

Frage anzeigen

Frage

Was ist das Problem beim Bubble Sort?

Antwort anzeigen

Antwort

Das Problem beim Bubblesort ist seine Effizienz. Große Elemente werden zunächst schnell am Ende einer Liste einsortiert. Kleinere Elemente werden jedoch nur langsam nach vorn verschoben. 

Frage anzeigen

Frage

Wann wird der Bubblesort hauptsächlich verwendet?

Antwort anzeigen

Antwort

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

Frage anzeigen

Frage

Wahr oder falsch

Der Bubble Sort kann sowohl iterativ als auch rekursiv implementiert werden.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Der Bubblesort arbeitet ______ (1), da immer zwei ______ (2) einer Datenmenge miteinander verglichen werden.

Antwort anzeigen

Antwort

(1) vergleichsbasiert

(2) Elemente  

Frage anzeigen

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
60%

der Nutzer schaffen das Bubble Sort Quiz nicht! Kannst du es schaffen?

Quiz starten

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

Kostenloser informatik Spickzettel

Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!

Jetzt anmelden

Finde passende Lernmaterialien für deine Fächer

Alles was du für deinen Lernerfolg brauchst - in einer App!

Lernplan

Sei rechtzeitig vorbereitet für deine Prüfungen.

Quizzes

Teste dein Wissen mit spielerischen Quizzes.

Karteikarten

Erstelle und finde Karteikarten in Rekordzeit.

Notizen

Erstelle die schönsten Notizen schneller als je zuvor.

Lern-Sets

Hab all deine Lermaterialien an einem Ort.

Dokumente

Lade unzählige Dokumente hoch und habe sie immer dabei.

Lern Statistiken

Kenne deine Schwächen und Stärken.

Wöchentliche

Ziele Setze dir individuelle Ziele und sammle Punkte.

Smart Reminders

Nie wieder prokrastinieren mit unseren Lernerinnerungen.

Trophäen

Sammle Punkte und erreiche neue Levels beim Lernen.

Magic Marker

Lass dir Karteikarten automatisch erstellen.

Smartes Formatieren

Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.

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

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration