Bubblesort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Visualisierung von Bubblesort

Bubblesort (auch Sortieren durch Aufsteigen) ist ein Algorithmus, der vergleichsbasiert eine Liste von Elementen sortiert. Dieses Sortierverfahren arbeitet in-place, sortiert stabil und hat eine Laufzeit von \mathcal{O}(n^2) im schlimmsten (Worst-Case) wie auch im durchschnittlichen Fall (Average-Case). Damit ist die Laufzeit asymptotisch suboptimal. In der Praxis wird Bubblesort kaum eingesetzt, da andere Verfahren ein besseres Laufzeitverhalten haben. Der Algorithmus spielt allerdings in der Lehre eine Rolle, da er als einfach zu erklären bzw. zu demonstrieren gilt. Des Weiteren eignet sich der Algorithmus um Techniken wie schrittweise Optimierungen, Laufzeit- bzw. Komplexitäts- und Korrektheitsanalyse einzuführen.

Prinzip[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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-k wird durch n-k Vertauschungen vollzogen. Aufsummieren über alle k ergibt im Ganzen 
\frac{1}{2}(n^2-n)=\Theta(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[Bearbeiten]

Falls die Liste bereits sortiert ist, 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

 Commons: Bubblesort – Sammlung von Bildern, Videos und Audiodateien