8.3 Der Bubblesort

Allgemeines

Der Bubblesort ("Blasen-Sortierung") ist der denkbar einfachste Sortieralgorithmus überhaupt. Bei jedem Sortierdurchgang werden zwei benachbarte Zahlen miteinander verglichen. Falls die rechte Zahl kleiner ist als die linke, werden die beiden Zahlen vertauscht. Dann wird eine Position weiter nach rechts gegangen und das Verfahren wiederholt. Nach dem ersten Durchgang befindet sich auf diese Weise die größte Zahl der Arrays ganz rechts. Es folgen weitere Durchgänge, bis schließlich alle Zahlen an der richtigen Position stehen.

Der Algorithmus

Durchgang 1

Am Anfang des ersten Durchgangs
Autor: Ulrich Helmich 05/2025, Lizenz: Public domain

Dieses Bild zeigt den ersten Schritt des ersten Durchgangs beim Bubblesort-Algorithmus. Der interne Zeiger (hier als roter Pfeil dargestellt) zeigt auf das erstes Arrayelement (Index i = 0).

Die beiden ersten Zahlen des Arrays werden verglichen (i=0 und i+1=1). Ist das Arrayelement zahl[i] größer als die Element zahl[i+1], was hier der Fall ist, so werden die beiden Elemente vertauscht:

   falls zahl[i] größer als zahl[i+1]
      dann tausche zahl[i] mit zahl[i+1] 

Die Methode tausche() vertauscht die beiden Arrayelemente mit den Indices i und i+1. Diese Methode müssen wir allerdings noch implementieren.

In Java müsste man diesen Pseudocode dann folgendermaßen formulieren:

   if (zahl[i] > zahl[i+1])
        tausche(i,i+1) 

Es reicht natürlich nicht, nur die beiden ersten Zahlen des Array zu vergleichen und zu vertauschen, sondern der ganze Array muss bearbeitet werden.

Im zweiten Schritt des ersten Durchgangs wird der interne Zeiger i (roter Pfeil) um 1 erhöht, und das Zahlenpaar zahl[i] und zahl[i+1] (jetzt hat i den Wert 1) wird wieder verglichen und gegebenenfalls vertauscht.

Der zweite Schritt des ersten Durchgangs und der Beginn des dritten Schritts
Autor: Ulrich Helmich 05/2025, Lizenz: Public domain

Da die 47 nicht größer ist als die 50, findet hier kein Tausch statt. Die Abbildung zeigt auch schon den Beginn des dritten Schrittes im ersten Durchgang. Der interne Zeiger i (roter Pfeil) verweist jetzt auf das Arrayelement mit dem Index i=2 und dem Wert 50. Die 50 wird nun mit der 62 verglichen, auch hier ist kein Tausch notwendig, die beiden Zahlen befinden sich bereits in der korrekten Reihenfolge.

Der erste Durchgang wird nun weiter fortgesetzt, bis die beiden letzten Zahlen des Arrays überprüft und gegebenenfalls vertauscht werden.

Die folgenden Schritte des ersten Durchgangs
Autor: Ulrich Helmich 05/2025, Lizenz: Public domain

Wenn der erste Durchgang abgeschlossen ist, steht die größte Zahl - hier die 62 - ganz am Ende des Arrays. Der Array ist nach dem ersten Durchgang allerdings noch nicht sortiert.

Bei einem kleinen Array aus vier oder fünf Zahlen könnte man natürlich die Befehle zum Vergleichen und Vertauschen hintereinander hinschreiben:

   i = 0;
   if ( zahl[i] > zahl[i+1] ) tausche (i,i+1);
   i = 1;
   if ( zahl[i] > zahl[i+1] ) tausche (i,i+1);
   i = 2;
   if ( zahl[i] > zahl[i+1] ) tausche (i,i+1);
   i = 3;
   if ( zahl[i] > zahl[i+1] ) tausche (i,i+1);
   i = 4;
   if ( zahl[i] > zahl[i+1] ) tausche (i,i+1);

Professionell ist das aber nicht, in einer Klausur würde das zu einem erheblichen Punktabzug führen. Vergleichen Sie den oberen Quelltext mit dem folgenden, der nicht nur das Gleiche leistet, sondern viel kürzer ist und vor allem auch locker einen Array mit 100 oder 1000 Zahlen bearbeiten kann:

   for (int i=0; i < MAX-1; i++)
      if ( zahl[i]) > zahl[i+1]  ) tausche(i,i+1)

Wir fangen vorne bei i = 0 an und hören bei i < MAX-1 auf. MAX ist übrigens die Zahl der Arrayelement. In unserem Beispiel hätte MAX also den Wert 6.

Angenommen, die for-Schleife würde erst bei i < MAX beendet werden. Wenn MAX den Wert 6 hat, wäre der letzte Wert der Laufvariable i also 5. Achten Sie auf die zweite Zeile des Quelltextes:

      if (zahl[i]) > zahl[i+1] )

Sehen Sie den Fehler? Wenn i den Wert 5 hat, hätte i+1 den Wert 6. Es würde also versucht werden, auf das Arrayelement zahl[6] zuzugreifen. Dieses Arrayelement gibt es aber gar nicht, das erste Element des Arrays hat den Index 0 und das letzte den Index 5.

Ende von Durchgang 1

Am Ende von Durchgang 1 sind die Zahlen des Arrays noch nicht sortiert. Das heißt, es sind weitere Durchgänge erforderlich, bis der Array wirklich sortiert ist. Man kann nun leicht abschätzen, wie viele dieser Durchgänge maximal erforderlich sind.

Weitere Durchgänge

Am Ende des ersten Durchgangs befindet sich die größte Zahl des Arrays am Ende, in unserem Beispiel also an Position 5.

Am Ende des zweiten Durchgangs ist die zweitgrößte Zahl an Position 4, am Ende des 3. Durchgangs ist Position 3 korrekt belegt, am Ende des 4. Durchgangs Position 2 und am Ende des 5. Durchgangs Position 1.

Wenn aber die Indices 1 bis 5 des Arrays richtig sortiert sind, dann ist auch das erste Arrayelement mit dem Index 0 an der korrekten Stelle. Der Bubblesort kann nach dem 5. Durchgang also abgebrochen werden.

Allgemein gilt: Ein Array, der aus MAX Elementen besteht, muss höchstens MAX-1 Sortierdurchgänge durchlaufen, damit er vollständig sortiert ist.

Die beiden Quelltext-Zeilen

   for (int i=0; i < MAX-1; i++)
      if ( zahl[i]) > zahl[i+1]  ) tausche(i,i+1)

müssen also in eine weitere (äußere) for-Schleife eingebettet werden:

   for (int d=1; d < MAX-1; d++)
        for (int i=0; i < MAX-1; i++)
             if ( zahl[i]) > zahl[i+1]  ) tausche(i,i+1)

Nach höchstens MAX-1 Durchgängen sollte der Array auf jeden Fall sortiert sein. Eine kleine Verbesserung der Laufzeit erreicht man, wenn man die innere for-Schleife optimiert:

   for (int d=1; d < MAX-1; d++)
        for (int i=0; i < MAX-1-d; i++)
             if ( zahl[i]) > zahl[i+1]  ) tausche(i,i+1)

Nach dem ersten Durchlauf befindet sich die größte Zahl des Arrays bereits am Ende. Der zweite Durchlauf muss also nicht mehr den gesamten Array durchgehen, sondern kann schon eine Position früher mit dem Vergleichen/Vertauschen aufhören. Beim dritten Durchlauf kann die innere for-Schleife schon zwei Positionen früher aufhören, weil die beiden letzten Arrayelemente ja bereits am richtigen Platz sind. Indem wir die Zahl der bereits absolvierten Durchläufe bei der inneren Schleife berücksichtigen, können wir die Sortierzeit etwas verkürzen.

Veranschaulichung des Bubblesort

Auf YouTube findet sich ein tolles Stop-Motion-Video zum Bubblesort. Drei Legomännchen sortieren hier zehn Säulen aus Lego-Steinen mithilfe des Bubblesort-Sortieralgorithmus. Sehr schön anzuschauen. Das Video muss unheimlich viel Arbeit gemacht haben -Respekt!

Die Methode tausche()

Die Java-Methode zum Vertauschen zweier Zahlen an den Positionen i und j in einem Array ist schnell implementiert:

private void tausche(int a, int b)
{
   int temp = zahl[a];
   zahl[a] = zahl[b];
   zahl[b] = temp;
}

Die Methode arbeitet nach dem Ringtausch-Prinzip:

Das Ringtausch-Prinzip der Methode tausche()
Autor: Ulrich Helmich 05/2025, Lizenz: Public domain

Übungen

Hier der Quelltext zur Messung des Zeitverhaltens:

public void zeitverhalten()
{
   final long timeStart = System.currentTimeMillis();
   System.out.println("Start der Messung:");	
   bubblesort();
   final long time = System.currentTimeMillis() - timeStart;
   System.out.println("Zeitdauer: "+time+" ms"+".");
}

Für Experten

Man kann den Quelltext zum Sortieren auch in eine eigene Klasse auslagern, die man zum Beispiel Sorter nennt. Wie das geht und welche Vorteile das bietet, wird in dem Lexikon-Artikel "Bubblesort (extern)" ausführlich dargestellt. Experten und solche, die es werden sollen, sollten sich diesen Abschnitt unbedingt ansehen.