BubbleSort

Beim Bubble Sort werden nacheinander jeweils zwei benachbarte Elemente in einer Datenstruktur (z.B. einem Array) miteinander verglichen. Ist das vorhergehende Element größer als das folgende Element, wird der Feldinhalt ausgetauscht. Zu diesem Zweck wird das Array von Links nach Rechts (Feld für Feld) durchgearbeitet. Mit unserem Beispielarray "Gebaeudereiniger" würde es für den ersten Sortiervorgang wie folgt aussehen:

gebaeudereiniger   =   g wird mit e getauscht
egbaeudereiniger   =   g wird mit b getauscht
ebgaeudereiniger   =   g wird mit a getauscht
ebageudereiniger   =   g wird mit e getauscht
ebaegudereiniger   =   g wird nicht mit u getauscht
ebaegduereiniger   =   u wird mit d getauscht
.
.
.
ebaegdereinigeru   =   u ist als größter Wert hinten angekommen

Nach dem ersten Durchlauf hat man also folgende Situation:
- das größte Element ist ganz rechts und
- alle anderen Elemente sind zwar teilweise an, bzw. näher an ihre endgültige Position gekommen, insgesamt ist es aber noch sehr unsortiert.

Dadurch das das größte Element an den anderen Elementen (wie eine aufsteigende Luftblase im Aquarium) vorbeizieht, trägt dieser Sortieralgorithmus den Namen Bubble Sort (bubble = englisch für Blase)

Zur Verdeutlichung hier nochmal ein Beispiel mit Zahlen:
4 9 3 2 5   =   unsortiertes Array
  3 9
    2 9
4 3 2 5 9   =   1. Durchlauf
3 4
  2 4
3 2 4 5 9   =   2. Durchlauf
2 3
2 3 4 5 9   =   3. Durchlauf
Eine Analyse der Durchgänge von Bubblesort:

Best case: O(n)    =    Array ist sortiert,
Aufwand = Anzahl der vorhandenen Elemente
Worst case: O(n 2)    =    Array ist total unsortiert,
Aufwand = Anzahl der Durchgänge * Anzahl der vorhandenen Elemente 2

Anmerkungen:
Mit Aufwand sind jeweils die Anzahl der Schleifendurchläfe gemeint.
Die kleinste Zahl wandert in der for-Schleife jeweils um eine Position nach links.
Wenn sie zu Beginn ganz rechts steht, so sind n - 1 Phasen nötig.

Average case: O(n 2)

Das folgende Struktogramm zeigt den Algorithmus schematisch:


Quellcode Bubble Sort in Pascal :

procedure bubble_sort (anz: integer; var a: feld);
var i, j, x : integer;
begin
	for i := 2 to anz do
		for j := anz downto i do
			if a[j - 1] > a[j]
			then begin
				x := a[j-1]
				a[j-1] := a[j]
				a[j] := x;
			     end;
end;
Quellcode Bubble Sort in C :
void bubble_sort (int anz, int a[])
{
	int i, j, x;
	
	for (i = 2; i <= anz; i++)
	{
		for (j = anz; j >= i; j--)
			if (a[j-1] > a[j])
			{
				x = a[j-1];
				a[j-1] = a[j];
				a[j] = x;
			}
	}
}
Legende : 
	anz 	= Anzahl der Elemente

	a 	= ein Array

	i, j, x = Hilfsvariablen


Da beim ersten Durchlauf der größte Wert seinen Platz am Ende der Datenstruktur findet, kann man davon ausgehen, daß beim zweiten Durchgang der zweitgrößte Wert seinen Platz an vorletzter Position in der Datenstruktur findet, der drittgrößte Wert dann beim dritten Durchgang usw. Im oben genannten Beispiel "gebaeudereiniger" benötigt Bubble Sort also maximal 15 Durchläufe um die Datenstruktur zu sortieren. Da aber in der Regel einzelne Elemente bei den jeweiligen Durchläufen ihren Platz verbesser oder sogar ihre Endposition erlangen, ist die Datenstruktur in diesem Beispiel bereits nach 7 Durchgängen sortiert. Da Bubble Sort aber in jedem Fall 15 Durchläufe machen würde, ist es sinnvoll den Algorithmus insofern zu optimieren indem man nach einem Durchgang überprüft ob überhaupt etwas getauscht wurde.

Anfang Zurück Weiter