Allgemeines
Der Bubblesort ("Blasen-Sortierung") ist einer der einfachsten Sortieralgorithmen. Bei jedem Sortierdurchgang werden jeweils 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 des 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 erste 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 das 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 Indizes 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 Arrays zu vergleichen und gegebenenfalls zu vertauschen, sondern das 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 Schritts 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 fortgesetzt, bis die beiden letzten Zahlen des Arrays überprüft und gegebenenfalls vertauscht wurden.
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. Das Array ist nach dem ersten Durchgang allerdings noch nicht vollständig sortiert.
Bei einem kleinen Array aus beispielsweise sechs Zahlen könnte man natürlich die Befehle zum Vergleichen und Vertauschen hintereinander schreiben:
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. Dieser leistet das Gleiche, ist aber viel kürzer und kann vor allem auch ohne Probleme ein Array mit 100 oder 1000 Zahlen bearbeiten:
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.
Frage
Warum müssen wir bei der Schleifenbedingung unbedingt i < MAX - 1 schreiben und nicht einfach i < MAX?
Angenommen, die for-Schleife würde mit der Bedingung i < MAX arbeiten. Wenn MAX den Wert 6 hat, wäre der letzte Wert der Laufvariablen 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 vollständig 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 steht die zweitgrößte Zahl an Position 4, am Ende des dritten Durchgangs ist Position 3 korrekt belegt, am Ende des vierten Durchgangs Position 2 und am Ende des fünften Durchgangs Position 1.
Wenn aber die Indizes 1 bis 5 des Arrays richtig sortiert sind, dann befindet sich auch das erste Arrayelement mit dem Index 0 an der korrekten Stelle. Der Bubblesort kann nach dem fünften Durchgang also beendet werden.
Allgemein gilt: Ein Array, das aus MAX Elementen besteht, benötigt höchstens MAX - 1 Sortierdurchgänge, damit es vollständig sortiert ist.
Die beiden Quelltextzeilen
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; 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 ist das Array auf jeden Fall sortiert. Eine kleine Verbesserung der Laufzeit erreicht man, wenn man die innere for-Schleife optimiert:
for (int d = 1; d < MAX; d++)
for (int i = 0; i < MAX - d; i++)
if (zahl[i] > zahl[i+1])
tausche(i, i+1);
Frage
Was wird dadurch erreicht?
Nach dem ersten Durchgang befindet sich die größte Zahl des Arrays bereits am Ende. Der zweite Durchgang muss also nicht mehr das gesamte Array durchgehen, sondern kann schon eine Position früher mit dem Vergleichen und Vertauschen aufhören. Beim dritten Durchgang kann die innere for-Schleife schon zwei Positionen früher aufhören, weil die beiden letzten Arrayelemente bereits am richtigen Platz stehen. Indem wir die Zahl der bereits absolvierten Durchgänge bei der inneren Schleife berücksichtigen, können wir die Zahl der notwendigen Vergleiche verringern und damit die Sortierzeit etwas verkürzen.
Aufgabe für Experten
Theoretisch könnte man den Bubblesort auch folgendermaßen optimieren:
Sobald in einem Durchgang nicht mehr getauscht werden musste, ist klar, dass das Array sortiert ist. Der Bubblesort kann dann abgebrochen werden.
Teilaufgabe 1 (ohne Lösungsvorschlag)
Schreiben Sie eine entsprechende Java-Methode
Teilaufgabe 2 (ohne Lösungsvorschlag)
Erweitern Sie das Programm so, dass die Zahl der Vergleiche bei beiden Bubblesort-Varianten mitgezählt wird. Überprüfen Sie dann, ob die erwähnte Optimierung tatsächlich zu weniger Vergleichen führt.
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
Übung 8.3-1
- Bringen Sie die Klasse Liste mit dem Bubblesort-Sortieralgorithmus auf Ihrem Rechner zum Laufen und testen Sie, ob alles korrekt funktioniert.
- Begründen Sie, wieso die Bedingung der inneren for-Schleife i < MAX-1-d eine Beschleunigung des Bubblesort darstellt.
- Überprüfen Sie experimentell, welchen Zeitvorteil diese Optimierung bewirkt.
Der auf die Übung 8.3-2 folgende Quelltext zeigt Ihnen, wie man die Systemzeit ausliest und zum Messen der Zeitdauer eines Sortieralgorithmus verwenden kann.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Übung 8.3-2
Theoretisch sollte die Sortierzeit mit dem Quadrat der Anzahl N der Zahlen wachsen.
- Begründen Sie, warum das so ist.
- Überprüfen Sie experimentell, ob diese theoretische Vermutung in der Praxis zutrifft. Dazu müssen Sie irgendwie die Zeit messen, die Ihr Rechner zum Sortieren von 100, 200, 400, 800, 1600, ... Zahlen benötigt.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
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.
Seitenanfang -
Weiter mit dem Selectionsort...