Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:start [06.02.2023 18:24] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:start [08.02.2023 08:47] (aktuell) – Frank Schiebel
@@ Zeile 15: / Zeile 15: @@
     * 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?
@@ Zeile 31: / Zeile 32: @@
 {{ :faecher:informatik:oberstufe:algorithmen:sorting:bubblesort:zeitung_vert.png?290 |}}
-  * Welcher Aufwand wird im //Worst Case// nötig? Finde eine Eingabe, die für Bubble Sort einen solchen Worst Case darstellt.
+  * 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.