Bubblesort

Bubblesort ist ein Wichs-Scheiß-Sortierverfahren, dass sich jeder Informatiker und ITA der Klasse ITA1A in den ***** schieben kann. Genauso wie die anderen Sortierverfahren ist dies verfallen von Unglück und Unmenschlichkeit. Bitte verwendet dieses Sortierverfahren NIEMALS und lasst es für immer in Ruhe! Und jetzt noch unnötiger Scheiß, damit die Seite gefüllt wird...

Prinzip

Bubblesort an einer Zahlenliste

In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei wird 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.

Algorithmus

Um die Darstellung des Algorithmus nicht künstlich zu komplizieren, wird im Folgenden als Vergleichsrelation $>$ (größer als) verwendet. Wie bei jedem vergleichbasierten Sortierverfahren kann diese auch durch eine andere Relation ersetzt werden, die eine totale Ordnung definiert.

Der Algorithmus in seiner einfachsten Form als Pseudocode:

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
      } // ende if
    } // ende innere for-Schleife
  } // ende äußere for-Schleife

Die Eingabe ist in einem Array gespeichert. Die äußere Schleife verringert schrittweise die rechte Grenze für die Bubble-Phase, da nach jedem Bubblen an der rechtesten Position das größte Element der jeweils unsortierten Rest-Eingabe steht. In der inneren Schleife wird der noch nicht sortierte Teil des Feldes durchlaufen. Dabei werden zwei benachbarte Daten vertauscht, wenn sie in falscher Reihenfolge sind (also das Sortierkriterium verletzen).

Allerdings nutzt diese einfachste Variante nicht die Eigenschaft aus, dass nach einer Iteration, in der keine Vertauschungen stattfanden auch in den restlichen Iterationen keine Vertauschungen mehr stattfinden. Der folgende Pseudocode berücksichtigt dies:

bubbleSort2(Array A)
  n = A.size
  do{
    swapped = false
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
        swapped = true
      } // ende if
    } // ende for
    n = n-1
  } while (swapped == true)

Die äußere Schleife durchläuft die zu sortierenden Daten, bis keine Vertauschungen mehr notwendig sind.

Eine weitere Optimierung besteht in der Ausnutzung der Eigenschaft, dass am Ende einer äußeren Iteration alle Elemente rechts von der letzten Tauschposition schon an ihrer endgültigen Position stehen:

bubbleSort3(Array A)
  n = A.size
  do{
    newn = 1
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
        newn = i+1
      } // ende if
    } // ende for
    n = newn
  } while (n > 1)

Beispiel

Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden.

Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte und vorletzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich letzte/vorletzte/vorvorletzte …

55 07 78 12 42 1. Durchlauf 07 55 78 12 42 07 55 78 12 42 07 55 12 78 42 Letzter Vergleich 07 55 12 42 78 2. Durchlauf 07 55 12 42 78 07 12 55 42 78 Letzter Vergleich 07 12 42 55 78 3. Durchlauf 07 12 42 55 78 Letzter Vergleich 07 12 42 55 78 4. Durchlauf + Letzter Vergleich 07 12 42 55 78 Fertig sortiert.

Komplexität

Beispiel, wie Bubblesort eine Liste sortiert. Die Listenelemente werden durch Balken dargestellt. Die x-Achse gibt an, wo sich ein Element in der Liste befindet, die Höhe gibt an, wie groß ein Element ist. Ein Frame entspricht einem Durchlauf. Animation starten

Ungünstigster Fall

Bubblesort hat die Laufzeit ${\mathcal {O}}(n^{2})$ für Listen der Länge $n$ . Im Falle der umgekehrt sortierten Liste (n, n-1, …, 2, 1) werden maximal ${\frac {n\cdot (n-1)}{2}}$ viele Vertauschungen ausgeführt: um das erste (und größte) Element $n$ ganz nach rechts zu bewegen, werden $n-1$ Vertauschungen vorgenommen. Allgemein: Die Bewegung des $k$ -ten Elements an die Stelle $n$ wird durch $n-k$ Vertauschungen vollzogen. Aufsummieren über alle $k$ ergibt im Ganzen ${\frac {1}{2}}(n^{2}-n)\in {\mathcal {O}}(n^{2})$ Vertauschungen. Da nur Paare vertauscht werden, die auch vorher verglichen wurden, benötigt der Algorithmus auch mindestens ebenso viele Vergleiche. Betrachtet man den Pseudocode des Algorithmus, so sieht man leicht ein, dass keine der Anweisungen öfter als ${\frac {1}{2}}(n^{2}-n)$ mal ausgeführt werden kann, also ist dies auch die bestmögliche untere Schranke.

Bester Fall

Bei einer bereits sortierten Liste wird Bubblesort die Liste nur einmal durchgehen, um festzustellen, dass die Liste bereits sortiert ist, weil keine benachbarten Elemente vertauscht werden mussten. Daher benötigt Bubblesort ${\mathcal {O}}(n)$ Schritte, um eine bereits sortierte Liste zu bearbeiten.

Falls die Elemente der Liste bereits nah den Stellen sind, die sie nach der Sortierung bekommen sollen, ist die Laufzeit erheblich besser als ${\mathcal {O}}(n^{2})$ .

Durchschnittlicher Fall

Die erwartete Anzahl der Vergleiche für eine zufällig gewählte Permutation der Liste (1, 2, …, n) ist

${\frac {1}{2}}{\Big (}n^{2}-n\cdot \ln n-(\gamma +\ln(2)-1)\cdot n{\Big )}+{\mathcal {O}}({\sqrt {n}})$ ,

wobei $\gamma$ die Euler-Mascheroni-Konstante bezeichnet; die erwartete Anzahl der Vertauschungen beträgt ${\frac {1}{4}}(n^{2}-n)$ .^[1]

Abgrenzung

Auch wenn Bubblesort nicht asymptotisch optimal ist, kann ein Einsatz für kleine Eingaben in Frage kommen, da für kleine $n$ die konstanten Laufzeitfaktoren eines Sortieralgorithmus dominieren, welche bei Bubblesort klein sind. Ein Anwendungsfall ist beispielsweise die Verwendung von Bubblesort in einem Basisfall eines rekursiv arbeitenden Sortierverfahrens.

Wenn die zu sortierende Eingabe (bis zu einer bestimmten Länge) mit einer hohen Wahrscheinlichkeit schon sortiert ist, eignet sich Bubblesort, da dies der Best-Case ist, in dem der Algorithmus eine lineare Laufzeit hat. Im Gegensatz dazu haben andere effiziente Sortierverfahren, wie z. B. Quicksort, oder asymptotisch optimale Verfahren, wie beispielsweise Mergesort, einen Best-Case von ${\mathcal {O}}(n\log n)$ .

In diesen Aspekten konkurriert Bubblesort mit Insertionsort, dessen Best-Case auch die schon sortierte Eingabe ist und die gleiche Komplexität wie Bubblesort hat (wie auch im Average- und Worst-Case). Außerdem ist Insertionsort, genauso wie Bubblesort, stabil und arbeitet ebenso in-place. Je nach Implementation hat Insertionsort geringere konstante Laufzeitfaktoren als Bubblesort.

Hasen und Schildkröten

Die Positionen der Elemente vor dem Sortieren entscheiden maßgeblich den Sortieraufwand von Bubblesort. Große Elemente am Anfang wirken sich nicht gravierend aus, da sie schnell nach hinten getauscht werden, kleine Elemente am Ende bewegen sich jedoch eher langsam nach vorne. Deswegen werden diese Elemente auch als Hasen bzw. Schildkröten bezeichnet.

Cocktailsort bubbelt alternierend Elemente von der linken und der rechten Seite, d. h. die dortige Bubble-Phase vermeidet das Problem von langsam nach vorne wandernden Elementen. Wegen der verwendeten Alternierung wird dieser Algorithmus auch Bidirectional-Bubblesort genannt. Im Worst-Case liegt seine Laufzeit, wie die von Bubblesort, in ${\mathcal {O}}(n^{2})$ .

Combsort ist mit Bubblesort verwandt. Wie Bubblesort vergleicht und tauscht er Elemente, aber im Unterschied zu Bubblesort werden, zur Vermeidung von langsam wandernden Elementen, auch weit auseinanderliegende Elemente verglichen und vertauscht. Seine Laufzeit ist im Worst-Case auch in ${\mathcal {O}}(n^{2})$ . Im Best-Case liegt sie in ${\mathcal {O}}(n\log n)$ (Bubblesort: ${\mathcal {O}}(n)$ ). Somit haben der Worst- bzw. Best-Case von Combsort und Quicksort die gleiche Komplexität.

Einzelnachweise

↑ Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 108–109 (englisch).

Literatur

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 38 (englisch).
Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 106–110 (englisch).

Weblinks

Commons: Bubblesort – Sammlung von Bildern, Videos und Audiodateien

[1] Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 108–109 (englisch).

[1]