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:

• 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?

• 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:

• 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:¹⁾

• 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.

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.