StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
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…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenDu 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 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 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!
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]:
Iterationen | Durchführung | Unsortiert | Sortiert | ||||||||||
Schritt 1 | Teile 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. | 5 | 2 | 8 | 4 | 9 | 7 | ||||||
Vergleiche nun das zweite und das dritte Element. Die 5 und die 8 sind bereits in der richtigen Reihenfolge. | 2 | 5 | 8 | 4 | 9 | 7 | |||||||
Die 8 und die 4 müssen wieder vertauscht werden. | 2 | 5 | 4 | 8 | 9 | 7 | |||||||
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. | 2 | 5 | 4 | 8 | 7 | 9 | |||||||
Schritt 2 | Der nächste Schritt beginnt wieder am Anfang des Arrays, die 2 und die 5 haben bereits die richtige Reihenfolge. | 2 | 5 | 4 | 8 | 7 | 9 | ||||||
Die 5 und die 4 müssen miteinander vertauscht werden. | 2 | 4 | 5 | 8 | 7 | 9 | |||||||
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. | 2 | 4 | 5 | 7 | 8 | 9 | |||||||
Schritt 3 | Gehe 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. | 2 | 4 | 5 | 7 | 8 | 9 |
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.
Nachdem Du ein Beispiel gesehen hast, hier noch einmal zusammengefasst, wie der Bubblesort Algorithmus abläuft:
Jetzt, wo Du weißt, wie Bubble Sort grundsätzlich funktioniert, stellt sich die Frage, wie es eigentlich mit der Komplexität aussieht?
Bei der Laufzeit des Bubble Sorts müssen der Best-Case, Average-Case und der Worst-Case voneinander unterschieden werden.
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).
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).
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!
Der Bubblesort Algorithmus arbeitet in-place. Außerdem besitzt er eine Platzkomplexität von O(1) – also einen konstanten zusätzlichen Speicheraufwand.
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:
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.
Bubblesort arbeitet vergleichsbasiert, da immer zwei Elemente einer Datenmenge miteinander verglichen werden.
Bubble Sort kann sowohl iterativ als auch rekursiv implementiert werden.
Um den Bubblesort zu parallelisieren, gibt es zwei unterschiedliche Möglichkeiten:
Beide Möglichkeiten machen den Bubblesort Algorithmus übrigens auch schneller.
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.
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.
In der folgenden Übersicht findest Du alles bisher gelernte zum Bubblesort noch einmal auf einen Blick:
Best-Case | Average-Case | Worst-Case | Platz-komplexität | Stabiles Verfahren | vergleichs-basiert | In-Place | Parallelisier-barkeit | iterativ/rekursiv |
O(n) | O(n2) | O(n2) | O(1) | Ja | Ja | Ja | Möglich | Beides |
Hier findest Du die Vor- und Nachteile des Bubblesort tabellarisch zusammengefasst:
Vorteile | Nachteile |
Einfacher, simpler Code | Ist 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.
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:
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.
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.
Um den Bubblesort für Dich noch etwas anschaulicher zu machen, folgen nun noch ein paar konkrete (Code-)Beispiele.
Wann wird Bubblesort hauptsächlich verwendet?
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.
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]
Odd-even Sort
Divide and Conquer
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.
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.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.