====== Bubblesort ======

Bubblesort ist ein einfacher und wenig performanter Sortieralgorithmus. Um das Array zu sortieren, durchläuft Bubble Sort das gesamte Array und vergleicht dabei jeweils benachbarte Elemente (das i-te Element wird mit dem i+1-ten Element verglichen). Ist das folgende Element kleiner als das aktuelle Element, werden die beiden Elemente vertauscht.


Anschließend wird das Array erneut durchlaufen, bis es sortiert ist:

{{ :faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:zeitung.png?290 |}}

----
{{:aufgabe.png?nolink  |}}

=== (A1) ===

    * Wieviele Vertauschungen haben stattgefunden, um die erste Zeile des dargestellten Sortiervorgangs zu erreichen?
    * Was geschieht bei jedem Durchlauf des Arrays jeweils? Kannst du erklären, woher der Name des Verfahrens kommen könnte?
    * Gibt es eine "Invariante", also eine Eigenschaft des Arrays, welche sich beispielsweise nach jeder Vertauschungsoperation oder nach jedem vollständigen Durchlauf durch das Array später nicht mehr verändert? 


----
{{:aufgabe.png?nolink  |}}

=== (A2) ===

  * Hole dir die Bluej-Vorlage von https://codeberg.org/qg-info-unterricht/algs4-sort-bluej. 
  * Implementiere Bubble-Sort zunächst mit zwei for-Schleifen, ohne Zwischenergebnisse auszugeben: 

{{ :faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:zeitung_oze.png?290 |}}

  * Ergänze deine Implementation um die Ausgabe eines Zwischenstatus nach jeweils einem ganzen Array-Durchlauf. Gib in der zweiten Spalte die Zahl der im letzten Durchlauf durchgeführten Vertauschungen an:((Die rote Färbung hat hier keine Bedeutung))

{{ :faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:zeitung_vert.png?290 |}}

  * Welcher Aufwand wird im //Worst Case// nötig - gib den Aufwand in O-Notation an. Finde eine Eingabe, die für Bubble Sort einen solchen Worst Case darstellt.


----
{{:aufgabe.png?nolink  |}}

=== (A3) ===

Shakersort (auch als "Cocktailsort" bekannt) ist eine Variante von
Bubblesort. Während Bubblesort das Array immer von links nach rechts bearbeitet, wechselt Shakersort nach jedem Durchgang die Richtung

  * Begründe, warum das Array {2, 3, 4, 5, ... , 99, 100, 1 } für Bubblesort einen Worst Case in Bezug auf die Anzahl der Vergleiche darstellt, für Shakersort aber nicht.
  * Kopiere die Bubble-Sort Klasse und implementiere Shakersort. Shakersort soll abbrechen, sobald ein Durchgang ohne Vertauschungen abgeschlossen wurde.