Bubblesort

Diese Seite entspricht dem Abi 17 (und folgenden)

Erklärvideos

• Bubblesort Prinzip

• Bubblesort Implementierung für Arrays

Fachbegriffe

Laufzeit, Bubblesort, Array, Index, Durchlauf, Tauschen, Nachfolger

Beschreibung des Verfahrens

Die Erläuterungen sind aus Wikipedia; vgl. [Wikipedia-Bubblesort]

In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei werden in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Die Bubble-Phase wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. Auch werden immer zwei Zahlen miteinander in „Bubbles“ vertauscht.

Laufzeit

im average case und im worst case: O(n²)

Implementierung für Arrays

Bubblesort ist das Sortierverfahren, das für Arrays am leichtesten zu implementieren ist - noch leichter als Insertionsort oder Selectionsort. Bubblesort geht auf Arrays wie folgt vor:

• Das Array wird (n-1)mal durchlaufen.
• Bei jedem Durchlauf wird von vorne nach hinten durch das Array gegangen.
• Wenn dabei ein Element größer ist als sein Nachfolger, dann tauschen die beiden die Plätze.

Implementierung mit mehreren Methoden

In dieser Implementierung wird der Algorithmus in drei Methoden zerlegt.

  private void bubblesort(Person[] personen){
     // (n-1)mal durchlaufen!
     for (int i = 0; i < personen.length-1; i++) {
        durchlauf(personen);
     }
  }
  
  private void durchlauf(Person[] personen) {
     // durch das ganze Array gehen
     for (int i = 0; i < personen.length-1; i++) {
        // Element mit dem Nachfolger vergleichen
        if(personen[i].istAlphabetischNach(personen[i+1])){
           // Plaetze tauschen
           tausche(personen, i, i+1);
        }
     }
  }

  // Sorgt dafuer, dass die Personen bei Index i und bei Index j 
  // die Plaetze tauschen.
  private void tausche(Person[] personen, int i, int j){
     Person hilfs = personen[i];
     personen[i] = personen[j];
     personen[j] = hilfs;
  }

Implementierung in einer Methode

Die Implementierung in einer Methode wird an einem Array mit int-Zahlen demonstriert.

public void bubblesort(int[] pArray) {
  for(int i=0; i<pArray.length-1; i++) {
    for(int j=0; j<pArray.length-1; j++) { 
      if(pArray[j] > pArray[j+1]){
        int zahl0 = pArray[j]; 
        int zahl1 = pArray[j+1];
        pArray[j] = zahl1;
        pArray[j+1] = zahl0;
      } 
    } 
  }
 }