Bubblesort
In diesem Beitrag findest du eine ausführliche Erklärung inklusive eines Bubblesort Beispiels mit Schritt-für-Schritt-Anleitung. Im Anschluss zeigen wir dir den Bubblesort Algorithmus mit einem Pseudocode und einem Bubblesort Struktogramm. Danach erfährst du alles Wichtige zur Komplexität und erfährst zum Schluss, wie ein Beispielcode für eine Bubblesort Java-, C- oder Python-Implementierung aussehen kann.
Willst du dich perfekt auf die kommende Prüfung vorbereiten, dann teste dein Wissen mit Hilfe unserer Klausuraufgabe . Spätestens nach der ausführlichen Musterlösung bleiben dann keine Fragen mehr offen!
Inhaltsübersicht
Erklärung
Der Grundgedanke des Sortieralgorithmus kommt tatsächlich von Luftblasen. Stell dir ein Glas gefüllt mit Mineralwasser vor. Darin steigen größere Luftblasen schneller auf als kleinere. Die sogenannten „Bubbles“ sortieren sich also der Größe nach. Deswegen kann das Sortierverfahren auch als „Sortieren durch Aufsteigen“ oder „Austauschsortieren“ bezeichnet werden.
Der Bubble Sort gehört zu den Sortieralgorithmen mit einem vergleichsbasierten Verfahren. Dabei ist das Sortierverfahren stabil und arbeitet in-place. Wegen seiner durchschnittlichen Zeitkomplexität von O(n²) gilt er als ziemlich langsam und wird deshalb in der Praxis kaum verwendet.
Prinzip
Beim Bubblesort Algorithmus wird ein Array – also eine Eingabe-Liste – immer paarweise von links nach rechts in einer sogenannten Bubble-Phase durchlaufen. Man startet also mit der ersten Zahl und vergleicht diese dann mit ihrem direkten Nachbarn nach dem Sortierkriterium. Sollten beide Elemente nicht in der richtigen Reihenfolge sein, werden sie ganz einfach miteinander vertauscht. Danach wird direkt das nächste Paar miteinander verglichen, bis die gesamte Liste einmal durchlaufen wurde. Die Phase wird so oft wiederholt, bis der gesamte Array vollständig sortiert ist.
1. Bubble-Phase
Die 5 ist größer als die 1, also tauschen wir die beiden miteinander. Als nächstes vergleichen wir die 5 mit der 4 und tauschen auch hier die Positionen. Danach wird die 5 mit der 9 überprüft. In diesem Fall wird kein Austausch benötigt. Diesmal ist die 5 kleiner und alles bleibt wie es ist. Weiter geht es dann mit der 9 und der 0 aber das Prinzip hast du jetzt bestimmt verstanden. Am Ende des Durchlaufs erhalten wir diese Liste:
[5] [1] [4] [9] [0] [8] [6]
[1] [5] [4] [9] [0] [8] [6]
[1] [4] [5] [9] [0] [8] [6]
[1] [4] [5] [9] [0] [8] [6]
[1] [4] [5] [0] [9] [8] [6]
[1] [4] [5] [0] [8] [9] [6]
[1] [4] [5] [0] [8] [6] [9]
2. Bubble-Phase
Die letzte Zahl auf der rechten Seite – in diesem Fall die 9 – ist nach der ersten Bubble-Phase auf ihrem richtigen Platz und muss nicht mehr überprüft werden. Jetzt kann die 2. Bubble-Phase starten und wir beginnen wieder von vorne und vergleichen zuerst die 1 mit der 4, dann die 4 mit der 0 und so weiter. Am Ende ist die 8 auf ihrem endgültigen Platz.
[1] [4] [5] [0] [8] [6] [9]
[1] [4] [5] [0] [8] [6] [9]
[1] [4] [5] [0] [8] [6] [9]
[1] [4] [0] [5] [8] [6] [9]
[1] [4] [0] [5] [8] [6] [9]
[1] [4] [0] [5] [6] [8] [9]
3. Bubble-Phase
[1] [4] [0] [5] [6] [8] [9]
[1] [4] [0] [5] [6] [8] [9]
[1] [0] [4] [5] [6] [8] [9]
[1] [0] [4] [5] [6] [8] [9]
[1] [0] [4] [5] [6] [8] [9]
4. Bubble-Phase
[1] [0] [4] [5] [6] [8] [9]
[0] [1] [4] [5] [6] [8] [9]
[0] [1] [4] [5] [6] [8] [9]
5. Bubble-Phase
[0] [1] [4] [5] [6] [8] [9]
[0] [1] [4] [5] [6] [8] [9]
6. Bubble-Phase
[0] [1] [4] [5] [6] [8] [9]
Nach dem 6. Durchlauf und dem letzten Vergleich erhalten wir die fertig sortierte Liste:
[0] [1] [4] [5] [6] [8] [9]
Bubblesort Algorithmus
Der Ablauf des Sortierverfahrens kann man als Pseudocode darstellen. Dafür braucht man erst das Verständnis, wie sich der Bubblesort Algorithmus allgemein aufbaut. Informell sieht das dann wie folgt aus:
bubblesort algorithmus
Einlesen einer Liste x.
Die gesamte Liste gilt zunächst als unsortiert (a).
Bedingung: Solange im unsortierte Bereich Elemente vorhanden sind,
soll der unsortierte Bereich von links nach rechts durchlaufen werden.
Wenn das linke Element (b) größer als das rechte Element (b+1) ist,
Elemente austauschen.
Das letzte Element gilt als sortiert und kann aus dem unsortierten Bereich entfernt werden.Pseudocode
Der Code ist natürlich vom Sortierkriterium abhängig. Wir gehen im folgenden Beispiel davon aus, dass ein Array der Größe nach aufsteigend sortiert werden soll. Das Ganze baut sich dann als Bubblesort Pseudocode folgendermaßen auf:
Bubble (Liste x)
laenge = x.Anzahl;
for b = 1 to laenge
for k = 0 to (laenge-b)
if zahl[k] > zahl[k+1]
c = zahl [k]
zahl[k] = zahl[k+1]
zahl[k+1] = cBubblesort Struktogramm
Das zugehörige Bubblesort Struktogramm bzw. Nassi-Schneidermann-Diagramm sieht wie folgt aus:
Bubblesort Laufzeit
In der Praxis wird der Sortieralgorithmus kaum verwendet. Grund hierfür ist seine sehr lange Laufzeit, weswegen sich andere Sortierverfahren deutlich besser eignen. Beispielsweise der Mergesort oder der Heapsort sind bei einem Datensatz im über vierstelligem Bereich tausendmal schneller.
Die Laufzeit im Average-Case beträgt genauso wie im Worst-Case O(n2) . Das liegt daran, dass der Algorithmus paarweise voranschreitet und damit entsprechend viele Paar vergleichen muss.
Nur im Best-Case kann er eine Laufzeit von O(n) erreichen. Das ist der Fall, wenn der Array bereits von Beginn an nach dem Sortierkriterium sortiert ist.
Die Berechnung von der Anzahl benötigter Vergleiche einer Datenfolge von der Länge n, lässt sich wie folgt darstellen:
Hier noch einmal die Bubblesort Laufzeit als Überblick:
- Worst-Case:
- Average-Case:
- Best-Case:
Klausuraufgabe
Wenn du dich optimal auf die Klausur vorbereiten möchtest, dann ist dieser Beitrag genau richtig für dich. Darin kannst du dich selbst an einer Aufgabe versuchen, wie sie dir in einer Prüfung begegnen kann. Natürlich besprechen wir die Lösung auch ausführlich.
Bubblesort Java
Passend zu dem oben erklärten Beispiel wird der folgende Bubblesort Java-Code als potentieller Weg zur Implementierung aufgebaut.
public class Bubble_Sort {
private int[] liste = {5, 1, 4, 9, 0, 8, 6};
public int[] sortieren() {
int a;
for(int k = 1; k < liste.length; k++){
for (int b = 0; b < (liste.length – k); b++) {
if (liste[b] > liste[b + 1]) {
a = liste[b];
liste[b] = liste[b + 1];
liste[b + 1] = a;
}
}
}
return liste;
}
public static void main(String[] args) {
Bubble_Sort bs = new Bubble_Sort();
int[] array = bs.sortieren();
for (int b = 0; b < array.length; b++) {
System.out.println(b + 1 + „:“ + array[b]);
}
}
}Bubblesort in C
Als Nächstes baut sich hier noch ein Quellcode einer beispielhaften C-Implementierung auf.
void bubble_sort(int *liste, int zahlen) {
int b, k,tmp;
for (k=1; k < zahlen; k++){
for(b = 0; b < (zahlen-k); b++){
if(liste[b] > liste[b+1]) {
tmp=liste[b+1];
liste[b+1]=liste[b];
liste[b]=tmp;
}
}
}
}
int main(void) {
int b;
int x_liste[] = { 5, 1, 4, 9, 0, 8, 6};
int a = sizeof(x_liste)/sizeof(int);
bubble_sort(x_liste, a);
for(b = 0; b < a; b++)
printf(„%d „, x_liste[b]);
printf(„\n“);
return EXIT_SUCCESS;
}Bubblesort Python
Zum Abschluss befindet sich hier noch eine mögliche Python-Implementierung.
def sorting(liste):
size_count = len(liste)
for i in range(1, size_count):
for k in range(0, size_count-i):
if(liste[k] > liste[k+1]):
swap(liste, k, k+1)
def swap(liste, start, end):
tmp = liste[end]
liste[end] = liste[start]
liste[start] = tmp
sorting_list = [5, 1, 4, 9, 0, 8, 6]
sorting(sorting_list)
print(sorting_list)