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

Der Bubblesort-Sortieralgorithmus ist ganz einfach:

Die beiden ersten Zahlen des Arrays werden verglichen. Ist die linke Zahl größer als die rechte, so werden die beiden 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.

Es reicht natürlich nicht, nur die beiden ersten Zahlen des Array zu vergleichen und zu vertauschen, sondern der ganze Array muss bearbeitet werden. Das regeln wir einfach mit einer for-Schleife:

   von i = 0 bis i < MAX-1
      falls zahl[i] größer als zahl[i+1]
         dann tausche zahl[i] mit zahl[i+1] 

Wir fangen vorne bei i = 0 an und hören bei i < MAX-1 auf.

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

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

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

Welchen Erfolg hätte der obige dreizeilige Quelltext? Nachdem alle Zahlenpaare (0,1), (1,2), (2,3), ... (MAX-2,MAX-1) verglichen und gegebenenfalls vertauscht worden sind, befindet sich die größte Zahl des Arrays an der letzten Position mit dem Index MAX-1.

Die anderen Zahlen des Arrays sind aber noch nicht sortiert, ein zweiter, ein dritter und noch weitere Durchgänge sind erforderlich, bis der gesamte Array sortiert ist.

Die obigen drei Quelltext-Zeilen müssen also in eine weitere for-Schleife eingebettet werden:

von durchlauf = 0 bis durchlauf < MAX-1
   von i = 0 bis i < MAX-1
      falls zahl[i] größer als zahl[i+1]
         dann tausche zahl[i] mit zahl[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:

   von i = 0 bis i < MAX-1-durchlauf

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 Implementation in Java

Wir bauen nun die Methode bubblesort() in unsere Klasse Liste ein, welche den gegebenen Array aus MAX Zufallszahlen nach dem oben beschriebenem Algorithmus sortiert.

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

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

Das Tauschen der Zahlen im Array wird hier durch die private Methode tausche() ausgeführt, die nach dem Ringtausch-Prinzip arbeitet.

Übungen

Hier der Quelltext zur Messung des Zeitverhaltens:

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

Für Experten (m/w/d)

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.