Index

Erstellen einfacher Programme

2. Algorithmen (11)


Sortieralgorithmen
- 4. Sortieren durch Austausch (Bubblesort)

Dieses Verfahren ist ähnlich dem Auswahlverfahren. Es werden jedoch nebeneinanderstehende Elemente verglichen. Ist das nachfolgende Element kleiner, so erflogt ein Austausch der betrachteten Vergleichs-Elemente. Danach rückt man eine Position weiter und vergleicht diese Elemente.

Unsortierte Liste:

90 20 12 72 2 51 47 80
1. Durchlauf:
90 20 12 72 2 51 47 80
20 90 12 72 2 51 47 80
20 12 90 72 2 51 47 80
20 12 72 90 2 51 47 80
20 12 72 2 90 51 47 80
20 12 72 2 51 90 47 80
20 12 72 2 51 47 90 80
20 12 72 2 51 47 80 90

Es ist leicht zu erkennen, dass die größte Zahl nach dem 1. Durchlauf auf dem letzten Platz steht.
Dies kommt daher, dass beim Vergleich und evtl. Austausch die größere Zahl rechts steht. Da aber diese mit der nächsten Zahl weiterverglichen wird, steht auch danach die größere Zahl wieder rechts. Es wird also gewissermaßen bei einem Durchlauf die größte Zahl unterwegs mitgeschleppt und ans Ende gebracht.

Beim zweiten Durchlauf müssen nur noch die Elemente links vom letzten verglichen werden. Es baut sich also von rechts her die sortierte Liste auf, wobei der unsortierte Teil links mit jedem Durchlauf um 1 kleiner wird.

2. Durchlauf:
20 12 72 2 51 47 80 90
12 20 72 2 51 47 80 90
12 20 72 2 51 47 80 90
12 20 2 72 51 47 80 90
12 20 2 51 72 47 80 90
12 20 2 51 47 72 80 90
12 20 2 51 47 72 80 90
3. Durchlauf:
12 20 2 51 47 72 80 90
12 20 2 51 47 72 80 90
12 2 20 51 47 72 80 90
12 2 20 51 47 72 80 90
12 2 20 47 51 72 80 90
12 2 20 47 51 72 80 90
4. Durchlauf:
12 2 20 47 51 72 80 90
2 12 20 47 51 72 80 90
2 12 20 47 51 72 80 90
2 12 20 47 51 72 80 90
2 12 20 47 51 72 80 90
5. Durchlauf:
2 12 20 47 51 72 80 90
2 12 20 47 51 72 80 90
2 12 20 47 51 72 80 90

Im 5. Durchlauf war kein Austausch erforderlich. Das bedeutet aber, dass die Elemente im unsortierten Teil in der richtigen Reihenfolge stehen, also dieser Teil nun ebenfalls sortiert ist. Damit kann man sich weitere Durchläufe sparen. Man muss das Verfahren also nicht immer bis zum bitteren Ende durchziehen.

Sortierte Liste:

2 12 20 47 51 72 80 90

Die größte Zahl "steigt" bei jedem Durchlauf nach rechts ähnlich den Luftblasen in einem Glas Wasser. Daher spricht man auch von Bubblesort.

Der Aufwand ist auch hier quadratisch zu n also (O(n²)). Im ungünstigsten Fall sind n(n - 1)/2 Vergleiche nötig und ebenso viele Austauschoperationen.

[Struktogramm] zu diesem Sortieralgorithmus.

[Index] [Zurück/Sortieren 3] [Fortsetzung/Sortieren 5]


Autor: Jürgen Dehmer
Letzte Änderung: 28. April 2001