Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/BubbleSort

BubbleSort

Dieses Kapitel behandelt die Suchmethode BubbleSort. Es handelt sich hierbei um ein sehr bekanntes, aber nicht besonders effizientes Sortierverfahren. Es ist eine einfach zu implementierende zugrunde liegende Vorstellung. Bei einer vertikalen Anordnung von Elementen in Form von Luftblasen (bubbles) werden wie in einer Flüssigkeit von alleine sortiert, da die größeren Blasen die kleiner „überholen“. Das Grundprinzip ist somit die Folge immer wieder zu durchlaufen und dabei benachbarte Elemente, die nicht die gewünschte Sortierreihenfolge haben, zu vertauschen. Das bedeutet Elemente die größer sind als ihre Nachfolger, überholen diese.

Beispiel

Java Code

void  BubbleSort(int[] F) {  
     
    for (int n= F.length; n >1; n=n-1) { 
      for (int i =0; i < F.length-1; i++)  {
           if (F[i] > F[i+1]){
               swap(F, i, i+1);
           }
       }
    }
}

Hierbei handelt es sich um die einfachste Form, doch der Algorithmus kann auch optimiert werden. Wir haben beobachtet, dass die größte Zahl in jedem Durchlauf automatisch an das Ende der Liste rutscht. Daraus folgt in jedem Durchlauf j reicht die Untersuchung bis Position n-j, das heißt im j.ten Durchlauf sind die Elemente zwischen den Positionen n-j und n-1 sortiert. Wenn keine Vertauschung mehr stattfindet, soll das Programm abbrechen.

void  BubbleSort(int[] F) {  
   boolean swapped;
   int n = F.length;
   do {
       swapped = false;
       for (int i =0; i < n-1; i++)  {
           if (F[i] > F[i+1]){
               swap(F, i, i+1);
               swapped = true;
           }
       }
       n--;
    }while (swapped);
  
}

Aufwand

Im besten Fall beträgt der Aufwand n. Im mittleren Fall ohne Optimierung $n^{2}$ und mit Optimierung ${\frac {n^{2}}{2}}$. Im schlechtesten Fall ohne Optimierung beträgt der Aufwand $n^{2}$ und mit Optimierung ${\frac {n^{2}}{2}}$.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.4 zu finden.