Logo: Titelseite, Fragezeichen: Hilfe, Liste: Externer Navigator, Pfeil: Nächste Seite

Bubblesort Animation


Methode

Der besondere einfache Ansatz für das Sortieren besteht darin, nur das Vertauschen benachbarten Datensätzen zuzulassen. So kann eine nach aufsteigenden Schlüsseln sortierte Folge von Datensätzen offensichtlich wie folgt hergestellt werden. Man durchläuft die Liste a[1],...,a[N] der Datensätze und betrachtet dabei je zwei benachbarte Elemente a[i] und a[i+1]. Nach diesem ersten Durchlauf ist das größte Element an seinem richtigen Platz am rechten Ende angelangt. Dann geht man die Folge erneut durch und vertauscht, falls nötig, wiederum je zwei benachbarte Elemente. Dieses Durchlaufen wird solange wiederholt, bis keine Vertauschungen mehr aufgetreten sind; d.h. alle Paare benachbarter Sätze stehen in der richtigen Reihenfolge. Damit ist das Feld a nach aufsteigenden Schlüsseln sortiert. Größere Elemente haben also die Tendenz, wie Luftblasen im Wasser langsam nach oben aufzusteigen. Diese Analogie hat dem Verfahren den Namen Bubblesort eingebracht.

Beispiel

Betrachten wir wieder das Feld a mit den sieben Schlüsseln 15, 2, 43, 17, 4, 8, 47. Beim ersten Durchlauf werden folgende Vertauschungen benachbarter Elemente durchgeführt.
15,2
2,15,43,17
17,43,4
4,43,8
8,4347,

Nach dem ersten Durschlauf ist die Reihenfolge der Schlüssel des Feldes a also
2, 15, 17, 4, 8, 43, 47.
Der zweite Durchlauf liefert die Reihenfolge
2, 15, 4, 8, 17, 43, 47.
Der dritte Durchlauf liefert schließlich
2, 4, 8, 15, 17, 43, 47,
also die aufsteigend sortierte Folge von Sätzen. Beim Durchlaufen dieser Folge müssen keine benachbarten Elemente mehr vertauscht werden. Das zeigt den erfolgreichen Abschluß des Sortierverfahrens.

Analyse

Die Abschätzung der im günstigsten und schlechtesten Fall ausgeführten Anzahlen von Schlüsselvergleichen ist einfach. Ist das Feld a bereits nach aufsteigenden Schlüsseln sortiert, so werden dabei keine Vertauschungen vorgenommen. Also ist
Cmin(N)=N-1, Mmin(N)=0.
Der ungünstigste Fall für das Verfahren Bubblesort liegt vor, wenn das Feld a anfangs nach absteigenden Schlüsseln sortiert ist. dann rückt das Element mit minimalem Schlüssel bei jedem Durchlauf um eine Position nach vorn. Es sind dann N Durchläufe nötig, bis es ganz vorn angelangt ist und festgestellt wird, daß keine Vertauschung mehr aufgetreten ist. Es werden beim i-ten Durchlauf (N-i) Vertauschungen benachbarter Elemente, also 3(N-i) Bewegungen, und natürlich jedesmal N-1 Schlüsselvergleiche ausgeführt. Damit ist:
Cmax=N(N-1)=O(N²)
Mmax=Summe(von i=1 bis N-1)3(N-i)=O(N²)

Man kann zeigen, daß auch
Mmit(N) = O(N²) gilt.

Animation

Um ein besseres Verständnis zu bekommen, können Sie den Ablauf des Algorithmus an der Animation verfolgen.Treten Sie jetzt in das Wasserparadies ein.

Schlussfolgerung

Bubblesort ist ein zwar durchaus populäres, aber im Grunde schlechtes elementares Sortier - verfahren. Nur für den Fall, daß ein bereits nahezu vollständig sortiertes Feld vorliegt, werden wenige Vergleichsoperationen und Bewegungen von Datensätzen ausgeführt.

Logo: Abteilungsseite, Pfeile: Seitenanfang, nächste Seite

Letzte Änderung 10. Februar 1998 ©