Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:start [06.02.2023 17:18] – angelegt Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:start [08.02.2023 08:47] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
 ====== Bubblesort ======
-Bubblesort ist ein einfacher und wenig performanter Sortieralgorithmus.
+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 |}}
 ----
@@ Zeile 9: / Zeile 13: @@
 === (A1) ===
-Hole dir die Bluej-Vorlage von https://codeberg.org/qg-info-unterricht/algs4-sort-bluej.
+    * 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.