faecher:informatik:oberstufe:algorithmen:sortieren:bubblesort:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
~~NOTOC~~


====== Bubble Sort ======


{{ :faecher:informatik:oberstufe:algorithmen:sortieren:bubblesort:mistkaefer.jpg?300|}}

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.| {{.:sortieren_bubble01.png?400px|}} |
|**Zweiter Durchlauf:**\\ -> 3 > 1, **Tauschen** \\ -> 3 < 4, **O.K.**\\ -> 4 > 2, **Tauschen**\\ -> 4 < 5, **O.K.** |  {{.:sortieren_bubble02.png?400px|}} |
| **Dritter Durchlauf:**\\ -> 1 < 3, **O.K.** \\ -> 3 > 2, **Tauschen**\\ -> 3 < 4, **O.K.**\\ -> 4 < 5, **O.K.** |  {{.:sortieren_bubble03.png?400px |}} | 


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


<note tip>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).</note>

----
{{:aufgabe.png?nolink  |}}
=== (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.((Für die Tabelle kann man auch nur die Zahlen nehmen und die Mistkugeln weglassen...))

{{  .:sortieren_bubble_aufgabe01.png?500px  |}}

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 =====
{{  .:auswahl_130.png?300|}}

{{:aufgabe.png?nolink  |}}
=== (A2) ===

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


  * Schreibe stichwortartig in die Felder, welchen Schritt des Algorithmus man ausführt und was genau dabei gemacht wird.
  * Notiere die Zahlenreihe und markiere bei jedem Schritt, welche Zahlen dort betrachtet werden.


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

===== Implementation des Algorithmus =====
{{:aufgabe.png?nolink  |}}
=== (A3) ===

  * Erstelle eine Methode ''bubblesort'' in der Klasse ''Musikliste'', die den Bubblesort-Algorithmus implementiert, um die Liste nach den Ratings zu sortieren. Es kann nötig sein, in der Klasse ''Song'' noch entsprechende getter-Methoden zu implementieren.
  * Zähle, wie viele Durchläufe durch alle Songs der ArrayList nötig sind, bis die Liste sortiert ist.
  * Lass dir die sortierte Liste ausgeben, um das Ergebnis zu kontrollieren.