Theorieteil zu Folge 8

Bubblesort

Sortieren durch Austauschen

Das Verfahren

Man beginnt am Anfang des Arrays. Zunächst wird zahl[0] mit zahl[1] verglichen, dann zahl[1] mit zahl[2] und so weiter, bis das Ende des Arrays erreicht ist. Ist eine Zahl größer als ihr rechter Nachbar, so werden die beiden Zahlen vertauscht. Durch diesen Prozess des Vergleichens und Tauschens wandert das größte Element an das Ende des Arrays. Nach dem ersten Durchgang besteht das Feld somit aus einem sortierten Teil der Länge 1 (am rechten Ende des Feldes) und einem unsortierten Teil der Größe N-1, wobei N für die Zahl der Elemente steht. Der Array ist noch nicht sortiert, lediglich das größte Element des gesamten Arrays wurde korrekt in den sortierten Teil eingeordnet. Es sind also weitere Durchgänge notwendig. Nach dem zweiten Durchgang ist das zweitgrößte Element korrekt einsortiert, nach dem dritten Durchgang das drittgrößte und so weiter. Insgesamt sind also N-1 Durchgänge erforderlich, um den Array zu sortieren.

Beispiel

Ein Array soll aus sechs int-Zahlen bestehen:

8
5
9
2
1
3
0
1
2
3
4
5

In der oberen Zeile sieht man die Werte der Array-Elemente, in der unteren Zeile die Indices der Elemente. Das erste Element hat den Index 0, das sechste Element den Index 5.

Durchgang 1

Zu Beginn werden die beiden ersten Zahlen miteinander verglichen - 8 und 5. Da die 8 größer ist als ihr rechter Nachbar, muss getauscht werden. Wir erhalten:

5
8
9
2
1
3
0
1
2
3
4
5

Während eben noch die Array-Elemente mit den Indices 0 und 1 miteinander verglichen wurden, müssen als Nächstes die Elemente Nr. 1 und 2 überprüft und ggf. vertauscht werden. Da die 8 aber kleiner ist als die 9, passiert nichts, und die nächsten beiden Elemente werden überprüft, die 9 und die 2. Hier muss wieder getauscht werden:

5
8
2
9
1
3
0
1
2
3
4
5

Nun werden die 9 und die 1 verglichen und getauscht:

5
8
2
1
9
3
0
1
2
3
4
5

Jetzt werden die beiden letzten Elemente verglichen und wieder getauscht:

5
8
2
1
3
9
0
1
2
3
4
5

Sie sehen selbst, dass der Array noch keineswegs sortiert ist. Der ganze beschriebene Vorgang war ja nur der erste Durchgang von möglicherweise vielen Durchgängen. Am Ende dieses ersten Durchgangs ist eines allerdings sicher: Die größte Zahl des Arrays steht ganz hinten. Insofern ist der hintere (rechte) Teil des Arrays bereits sortiert:

5
8
2
1
3
9
0
1
2
3
4
5

Dieser sortierte Teil kann beim nächsten Durchgang ignoriert werden. Spielen wir auch diesen zweiten Durchgang noch einmal Schritt für Schritt durch.

Durchgang 2

Die beiden ersten Elemente des unsortierten Teils werden verglichen. Da 5 < 8 ist, passiert nichts, und die beiden nächsten Elemente, 8 und 2, werden verglichen und getauscht:

5
2
8
1
3
9
0
1
2
3
4
5

Nun werden die beiden nächsten Elemente verglichen und vertauscht:

5
2
1
8
3
9
0
1
2
3
4
5

Dann die beiden nächsten Elemente:

5
2
1
3
8
9
0
1
2
3
4
5

Die 8 und die 9 müssen nicht mehr verglichen werden, da das Ergebnis ja bereits bekannt ist. Am Ende dieses zweiten Durchgangs befinden sich die beiden größten Zahlen am Ende des Arrays, der sortierte Teil des Arrays ist um ein Element gewachsen:

5
2
1
3
8
9
0
1
2
3
4
5
Weitere Durchgänge

Wie viele Durchgänge brauchen wir jetzt, um den Array komplett zu sortieren? Eine Obergrenze finden wir, wenn wir uns die letzte Abbildung anschauen. Im dritten Durchgang kommt die 5 an die Position 3:

2
1
3
5
8
9
0
1
2
3
4
5

Im vierten Durchgang kommt die 3 an Position 2, wo sie sich aber auch schon nach dem dritten Durchgang befunden hat. Nach dem dritten Durchgang war der Array aber noch nicht sortiert, die 2 und die 1 müssen noch vertauscht werden, also ist auf jeden Fall ein vierter Durchgang notwendig:

1
2
3
5
8
9
0
1
2
3
4
5

Nach dem vierten Durchgang befindet sich die 3 (immer noch) an der korrekten Position. Der unsortierte Teil besteht nur noch aus zwei Elementen. In unserem Beispiel sind diese bereits sortiert. Rein theoretisch wäre aber auch eine Konstellation denkbar, in der die beiden vorderen Elemente noch vertauscht werden müssen. Also ist ein fünfter Durchgang unter Umständen nötig. Um herauszufinden, ob ein fünfter Durchgang notwendig ist, wird Rechenzeit benötigt. Da ist es fast einfacher und schneller, den fünften Durchgang einfach ohne Rückfrage durchzuführen, selbst wenn er nichts mehr bringt.

1
2
3
5
8
9
0
1
2
3
4
5

So sieht der Array nach dem fünften Durchgang aus.

Ein sechster Durchgang ist aber nun nicht mehr notwendig, denn der unsortierte Teil besteht aus nur noch einem Element.

Wenn wir jetzt verallgemeinern, so können wir behaupten: Wenn ein Array aus N Elementen besteht, so sind maximal N-1 Durchgänge notwendig, um ihn zu sortieren.

Implementationshinweise

Normalerweise setzt man zwei ineinander verschachtelte for-Schleifen ein, wenn man einen Bubblesort implementieren möchte. Die innere for-Schleife durchläuft den Array von vorne nach hinten und korrigiert eventuelle Fehlstellungen durch sofortiges Austauschen. Die äußere for-Schleife ist dafür verantwortlich, dass dieser Vorgang so oft aufgerufen wird, bis der gesamte Array sortiert ist.

Zurück zu Folge 8

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 27. Februar 2005 und verändert am 1. Oktober 2006. Geringfügige Veränderungen wurden am 6. August 2007 vorgenommen.





IMPRESSUM