Theoretische Informatik

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.

Bubblesort, Bubble Sort
direkt ins Video springen
Bubblesort

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.

Jetzt neu
Teste Dein Wissen mit Übungsaufgaben

Bubblesort Beispiel

Innerhalb des Bubblesort Beispiels wird das folgende Array aufsteigend sortiert:

[5] [1] [4] [9] [0] [8] [6]

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] = c

Bubblesort Struktogramm

Das zugehörige Bubblesort Struktogramm bzw. Nassi-Schneidermann-Diagramm sieht wie folgt aus:

Bubblesort Struktogramm, Struktogramm Bubblesort, Bubble Sort Struktogramm, Nasi-Schneidermann-Diagramm
direkt ins Video springen
Bubblesort Struktogramm

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:
n-1+n-2+...+1 = \frac{(n∙(n-1))}{2} \in O(n^2)

Hier noch einmal die Bubblesort Laufzeit als Überblick:

  • Worst-Case: O(n^2)
  • Average-Case: O(n^2)
  • Best-Case: O(n)

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.

Klausuraufgabe, Bubblessort
Klausuraufgabe zum Bubblesort

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)
Jetzt neu
Teste Dein Wissen mit Übungsaufgaben

Andere Nutzer halten diese Inhalte aus dem Bereich „Theoretische Informatik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.