|
Das Prinzip ist folgendes: Durchlaufe immer wieder das Feld und vertausche jedesmal, wenn es notwendig ist, benachbarte Elemente; wenn bei einem Durchlauf kein Austausch mehr erforderlich ist, ist das Feld sortiert. Eine Implementation des Verfahrens wird nachfolgend angegeben:
void bubblesort (int a[ ], int N)
{
int i, j, x;
for ( i = n; i >= 2; i--)
for ( j = 1; j < i; j++)
if ( a[j] > a[j+1])
{
x = a[j];
a[j] = a[j+1];
a[j+1] = x;
}
}
Man muß etwas nachdenken, um sich davon zu überzeugen, daß dieser Weg überhaupt zum Ziel führt. Hierzu bemerken wir, daß jedesmal, wenn während des ersten Durchlaufs das maximale Element vorgefunden wird, dieses mit jedem der rechts von ihm befindlichen Elemente vertauscht wird, und dies so lange, bis es die Position am rechten Ende des Feldes erreicht hat. Während des zweiten Durchlaufs wird dann das zweitgrößte Element an die richtige Position bewegt usw. Somit läuft der Bubble Sort wie eine Abart des Selection Sort ab, obwohl viel mehr Aufwand getrieben wird, um jedes Element an die richtige Position zu bringen.
i = 8: i = 4:
j = 1 2 3 4 5 6 7 j = 1 2 3
x= 23 55 63 x = 04
i = 7: i = 3:
j = 1 2 3 4 5 6 j = 1 2
x = 23 55 x =
i = 6: i = 2:
j = 1 2 3 4 5 j = 1
x = 16 23 x =
i = 5:
j = 1 2 3 4
x = 07 16
Abbildung 3 Bubble Sort
|
