Bubble Sort

Oje, Willi hat seine Mistkugeln auf offenem Feld aufgereiht. Ein heftiger Windstoss und die Kugeln rollen davon und liegen schon wieder in einem Durcheinander. Also nochmals sortieren. Willi ist noch ganz erschöpft von seiner ersten Sortier-Aktion. Vor allem das Suchen der "falschen" Paare war sehr anstrengend! Er musste dabei immer die ganze Kugelreihe überblicken.

Gut, ich machs nochmals, sagt er sich, aber diesmal ein bisschen systematischer. Er sucht die "falschen" Paare jetzt nicht mehr nach dem Zufallsprinzip, sondern geht von links nach rechts durch die Reihe. Dabei vergleicht er immer zwei benachbarte Kugeln. Sobald er zwei Kugeln mit falscher Reihenfolge gefunden hat, vertauscht er diese. Nachdem er die ganze Reihe so abgearbeitet hat, beginnt er wieder vorn vorne, d.h. von links. Wenn es schon mit Zufall geklappt hat, denkt sich Willi, dann muss es doch mit System erst recht klappen. Vielleicht sogar noch schneller als vorher? Tatsächlich findet er nach einigen Durchgängen kein "falsches" Paar mehr…

Schritt für Schritt...

Erster Durchlauf:
Es wird von links nach rechts jeweils die Mistkugel mit ihrem rechten Nachbarn verglichen.
Ist die rechte größer als die Linke, passiert nichts, ist die Linke größer als die rechte werden die beiden vertauscht.
→ 3 ist kleiner als vier, O.K., weiter zum 2. Element
→ 4 ist größer als 1, Tauschen. Weiter zum nächsten Element, dem dritten
- nach dem Tausch ist das wieder die 4!
→ 4 ist kleiner als 5, O.K., weiter zun nächsten Element
→ 5 ist größer als 2, Tauschen. Weitergehen zu ELement vier.
Durchlauf zu Ende.
Zweiter Durchlauf:
→ 3 > 1, Tauschen
→ 3 < 4, O.K.
→ 4 > 2, Tauschen
→ 4 < 5, O.K.
Dritter Durchlauf:
→ 1 < 3, O.K.
→ 3 > 2, Tauschen
→ 3 < 4, O.K.
→ 4 < 5, O.K.

Bei einem vierten Durchlauf würde man keine Vertauschung mehr benötigen - die Mistkugeln sind sortiert.

Wenn man sich anstelle der Mistkugeln Luftblasen in einem Aquarium vorstellt und das Ganze um 90° gegen den Uhrzeigersinn dreht, sieht man in Gedanken, wie die Luftblasen im Wasser aufsteigen. Zuerst die grösste ganz nach oben, dann die zweitgrösste usw. Die Vorstellung von den steigenden Luftblasen hat diesem Sortierverfahren seinen Namen gegeben: BubbleSort (bubble (engl.) = Blase).

(A1)

Sortiere auf einem Blatt Papier mit dem BubbleSort Verfahren die folgende Mistkugelreihe. Fertige eine Tabelle an, in der jeder Durchlauf des Sortierverfahrens zu erkennen ist, markiere die Vertauschungen.1)

Beobachte die Postion der jeweils größten Kugeln, die noch nicht an ihrem endgültigen Platz sind - was fällt dir auf?

Der Algorithmus

Wir sehen im Beispiel oben sofort, dass die Reihe nach dem dritten Durchgang sortiert ist und wir damit fertig sind. Wie aber kann ein Programm herausfinden, ob eine Reihe sortiert ist? Um zu entscheiden, ob die Reihe sortiert ist, kann unser Programm also einen weiteren Durchgang ausführen. Wenn in einem Durchgang kein "falsches" Paar mehr gefunden wird, sind wir fertig.

Diese Überlegungen führen uns auf folgenden Algorithmus:

Schritt Was ist zu tun?
(1) Wähle die ersten beiden Elemente von links.
(2) Ist beim gewählten Paar das linke Element grösser als das rechte? Wenn ja, vertausche die beiden.
(3) Hat es rechts des soeben untersuchten Paares noch weitere Kugeln? Wenn ja, wähle das nächste Paar benachbarter Elemente und gehe zu (2).
(4) Wir haben einen Durchgang beendet. Wurde in diesem Durchgang mindestens ein "falsches" Paar gefunden und vertauscht? Wenn ja, gehe zu (1), d.h. starte einen weiteren Durchgang. Wenn nein, sind wir fertig.

Anwendung des Algorithmus auf das Eingangsbeispiel

(A2)

In der Datei sortieren_bubble.pdf (ODS) ist der erste Durchgang gemäß des Algorithmus notiert. Fülle die Tabelle vollständig aus:

Warum sind vier Durchläufe nötig? Erkläre!

Implementation des Algorithmus

(A3)

1)
Für die Tabelle kann man auch nur die Zahlen nehmen und die Mistkugeln weglassen…