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?

• 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? Finde eine Eingabe, die für Bubble Sort einen solchen Worst Case darstellt.