4.2.1 Der Bubblesort

Allgemeines zum Bubblesort

Der Bubblesort-Algorithmus gehört zu den einfachsten bekannten Sortierverfahren. In jedem Durchlauf werden jeweils zwei benachbarte Elemente miteinander verglichen. Ist das rechte Element kleiner als das linke, erfolgt ein Tausch der beiden Werte. Anschließend wird zur nächsten Position übergegangen, und der Vergleich wird wiederholt. Nach dem ersten vollständigen Durchlauf steht das größte Element des Arrays bereits an der letzten Position. Durch weitere Durchläufe "wandern" nach und nach alle größeren Elemente nach rechts, bis schließlich das gesamte Array vollständig sortiert ist.

Der Begriff "Bubblesort"

Der Begriff "Bubblesort" beschreibt anschaulich das Verhalten der Elemente während des Sortierens. Das Bild stammt aus der Physik: In einer Flüssigkeit steigen Luftblasen ("bubbles") nach oben.

Beim Bubblesort verhalten sich die größeren Elemente ähnlich wie solche Luftblasen: Sie "steigen" bei wiederholten Vergleichs- und Tauschoperationen schrittweise nach oben, also im Array nach rechts (bei aufsteigendem Sortieren). In jedem Durchlauf rücken größere Werte ein Stück weiter an ihr korrektes Ende des Arrays, bis sie schließlich ihre endgültige Position erreicht haben.

Der Name verdeutlicht also das typische Arbeitsprinzip des Algorithmus: Durch wiederholtes Vergleichen und Tauschen "wandern" die großen Elemente wie Blasen nach oben, während kleinere Elemente weiter links verbleiben.

Der Bubblesort-Algorithmus

Durchgang 1

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

Zu Beginn des ersten Durchgangs werden die beiden Zahlen zahl[0] und zahl[1] verglichen. Die Laufvariable i der zuständigen for-Schleife hat den Wert 0.

Das Tauschen

Ist das Arrayelement zahl[0] größer als die Element zahl[1], was hier der Fall ist, so werden die beiden Elemente vertauscht:

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

Eine Methode tausche(i,j) hatten wir bereits in der Folge 4 implementiert, bei den Übungen zu den Arrays. Hier der vollständige Quelltext einer solchen Methode in zwei Versionen.

Version 1: einfaches Tauschen ohne vorherige Kontrolle

    private void tausche(int indexA, int indexB)
    {
        int temp = zahlen[indexA];
        zahlen[indexA] = zahlen[indexB];
        zahlen[indexB] = temp;
    }

Version 2: Tauschen mit Kontrollen

    private void tausche(int indexA, int indexB)
    {
        if (indexA < 0 || indexB < 0) return;
        if (indexA >= MAX-1 || indexB >= MAX-1) return;
        if (index A == indexB) return;
		  
        int temp = zahlen[indexA];
        zahlen[indexA] = zahlen[indexB];
        zahlen[indexB] = temp;
    }

Bei Indices kleiner als Null oder größer als der Index des letzten Arrayelements bricht die Methode sofort ab. Auch wenn beide Indices gleich sein sollten, bricht die Methode ab, da ein Tausch hier nicht erforderlich ist. Wenn die Methode bubblesort() allerdings korrekt implementiert wurde, braucht man diese drei Kontrollen überhaupt nicht, da keiner der drei Fälle eintreten kann, wenn man bei der Gestaltung der for-Schleife aufpasst.

Überprüfung der nächsten Elemente

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

Im zweiten Schritt des ersten Durchgangs wird die Laufvariable 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
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Da die 47 nicht größer ist als die 50, findet hier kein Tausch statt. Auch die beiden nächsten Zahlen, die 50 und die 62, befinden sich bereits in korrekter Reihenfolge und müssen nicht vertauscht werden. Dann werden die 62 und die 19 vertauscht, und danach die 63 und die 23:

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. Die erste "Blase" ist quasi nach oben gestiegen.

Das Array ist nach dem ersten Durchgang allerdings noch nicht sortiert.

Java-Quelltext für einen Durchgang

Hier der Java-Quelltext für einen solchen Durchgang, genauer gesagt, für den ersten Durchgang:

   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 Arrayelemente. 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. Ein Array-out-of-bounds-Fehler wäre die Folge, das Programm würde abstürzen.

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 das 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 Elemente an den 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 MAX-1 mal durchlaufen werden, dann ist das Array mit Sicherheit sortiert. Wir betten die beiden obigen Quelltext-Zeilen daher in eine äußere for-Schleife ein, die von 1 bis MAX-1 zählt:

   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)

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.

Übungen

Die Klassen Date und System bieten Methoden zur Millisekunden und sogar Nanosekunden genauen Messung der Zeit an. Allerdings hängen die gemessenen Zeitdifferenzen stark von der Belastung des Systems ab, auf denen das Programm gerade läuft. Mal dauert das Sortieren von 20.000 Zahlen etwas länger, unter anderen Bedingungen geht es wieder etwas schneller.

Eine völlig andere Methode zur Erfassung des Zeitverhaltens ist das Zählen von Vergleichen und Zuweisungen in dem Quelltext selbst. Dazu müssen Sie eine Instanzvariable operationen in die Klasse einbauen, die jedes Mal inkrementiert wird, wenn Sie einen Vergleich oder eine Zuweisung in dem Algorithmus durchführen. Für einen Tauschvorgang werden drei Zuweisungen benötigt, hier muss operationen sogar um 3 inkrementiert werden. Am Ende des Sortiervorgangs geben Sie dann einfach den Wert von operationen aus, und so können Sie zuverlässig vergleichen, wie viele Operationen für das Sortieren von 100, 200, 300, ... 1.000 Zahlen benötigt werden.

Eine kleine Optimierung des Bubblesort

Für das Sortieren von 200 int-Zahlen werden nach Summierung aller Vergleichs- und Zuweisungsoperationen ca. 46.000 Operationen benötigt. Das Quadrat von 200 ist 40.000, daher gehen wir jetzt einfach mal von dieser Zahl aus.

Angenommen, wir würden den Array vor dem Sortieren in zwei Teil-Arrays mit je 100 Zahlen aufteilen. Dann würden wir für das Sortieren des linken Teilarrays 100 x 100 = 10.000 Operationen benötigen, und für das Sortieren des rechten Teilarrays ebenfalls 10.000 Operationen.

Die beiden sortierten Teilarrays müssten dann "nur noch" zusammengefügt werden. Dazu benötigen wir eine merge()-Methode. Diese durchläuft beide Teilarrays und fügt dann die jeweils kleinere Zahl in den neu zu erstellenden Ziel-Array ein. Aus den beiden 5er Arrays

3 - 5- 7- 8 - 10

2 - 6 - 7 - 9 - 11

würde dann der Zielarray

2 - 3- 5- 6- 7 - 7- 8- 9 - 10 - 11

entstehen.

Jeder Teilarray wird dabei nur einmal von vorne nach hinten durchlaufen, die Rechenzeit für das Mergen (Zusammenführen) wächst also linear mit der Länge der Teilarray und spielt daher bei der Ermittlung der gesamten Rechenzeit für das Sortieren so gut wie keine Rolle.

Durch das Aufteilen des Arrays in zwei Hälften, sortieren der beiden Hälften und zusammenfügen der Hälften hätten wir die Rechenzeit also von 40.000 Operationen auf 20.000 Operationen reduziert.

Der Merge-Algorithmus

    public int[] merge()
    {
        int[] ergebnis = new int[links.length + rechts.length];

        int i = 0; // Index links
        int j = 0; // Index rechts
        int k = 0; // Index ergebnis

        // Solange beide Hälften noch Elemente übrig haben
        while (i < links.length && j < rechts.length)
        {
            if (links[i] <= rechts[j])
            {
                ergebnis[k] = links[i];
                i++;
            }
            else
            {
                ergebnis[k] = rechts[j];
                j++;
            }
            k++;
        }

        // Rest der linken Hälfte (falls vorhanden)
        while (i < links.length)
        {
            ergebnis[k] = links[i];
            i++;
            k++;
        }

        // Rest der rechten Hälfte (falls vorhanden)
        while (j < rechts.length)
        {
            ergebnis[k] = rechts[j];
            j++;
            k++;
        }

        return ergebnis;
    }

Erklärung des Merge-Algorithmus

int[] ergebnis = new int[links.length + rechts.length];

Das ist das Ziel-Array ergebnis[]. Die Länge dieses Ziel-Array ist die Summe der Länge der beiden Teil-Arrays links[] und rechts[]. Schließlich müssen ja alle Zahlen der beiden Teil-Arrays in den Ziel-Array hineinpassen. Die merge()-Methode geht davon aus, dass das ursprüngliche Array bereits in die beiden Teil-Arrays aufgeteilt wurde.

Für das Zusammenfügen der beiden Teil-Arrays benötigen wir drei lokale Hilfsvariablen:

1. i zeigt auf das aktuelle Element in dem Array links[],
2. j zeigt entsprechend auf das aktuelle Elemente im Array rechts[],
3. k zeigt auf die nächste freie Position im Ziel-Array ergebnis[].

Kommen wir nun zu der ersten while-Schleife, der Haupt-Schleife. Solange beide Hälften noch Elemente übrig haben (i < links.length && j < rechts.length), vergleichen wir links[i] mit rechts[j].

Das kleinere (oder gleiche) Element übernehmen wir nach ergebnis[k] und erhöhen dann den entsprechenden Index des Teil-Arrays, also i oder j, und anschließend auch den Index k.

Wenn eine Hälfte "aufgebraucht" ist, kann die andere Hälfte durchaus noch Elemente übrig haben. Diese sind aber bereits sortiert und werden in einem Rutsch an das Ende von ergebnis[] kopiert. Für diese Kopier-Aktion sind die beiden kleineren while-Schleifen am Ende der Methode verantwortlich.

Am Ende der Methode ist das Ziel-Array ergebnis[] sortiert und kann dann von der Methode als Array zurückgegeben werden.