Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- modul:m323:learningunits:lu01:tracetable [2024/08/06 16:43] – kmaurizi
+++ modul:m323:learningunits:lu01:tracetable [2024/08/06 16:47] (aktuell) – kmaurizi
@@ Zeile 40: / Zeile 40: @@
 | 7 | 3 | - | - | - | - | [1, 2, 3, 4] |
-===== Detaillierte Analyse des Beispiels =====
+==== Detaillierte Analyse des Beispiels ====
   * **Schritt 1-3**: Während der ersten Schleifeniteration wird das größte Element (4) nach rechts verschoben. Jeder Vergleich, bei dem ein größeres Element links von einem kleineren liegt, führt zu einem Tausch. Der Trace Table zeigt genau, wie sich die Liste in jedem Schritt ändert.
@@ Zeile 46: / Zeile 46: @@
   * **Schritt 6**: In der dritten Iteration sind keine weiteren Swaps notwendig, da die Liste bereits sortiert ist.
   * **Schritt 7**: Die vierte Iteration ist nur eine formale Überprüfung, da keine weiteren Vergleiche mehr nötig sind.
+===== Rekursives Bubble Sort Beispiel =====
+Nun erweitern wir das Beispiel mit einer rekursiven Implementierung des Bubble Sort. Der rekursive Ansatz arbeitet, indem er die Liste iterativ sortiert, bis keine weiteren Vertauschungen mehr notwendig sind.
+<code python>
+def bubble_sort_recursive(zahlen, n):
+    if n == 1:
+        return
+    for i in range(n - 1):
+        if zahlen[i] > zahlen[i + 1]:
+            zahlen[i], zahlen[i + 1] = zahlen[i + 1], zahlen[i]
+    bubble_sort_recursive(zahlen, n - 1)
+zahlen = [4, 3, 1, 2]
+bubble_sort_recursive(zahlen, len(zahlen))
+</code>
+Ein Trace Table für diese rekursive Version könnte folgendermaßen aussehen:
+^ Schritt ^ n ^ i ^ zahlen[i] ^ zahlen[i+1] ^ Vergleich (zahlen[i] > zahlen[i+1]) ^ Array-Zustand ^ Rekursionsaufruf ^
+| 1 | 4 | 0 | 4 | 3 | Ja | [3, 4, 1, 2] | Nein |
+| 2 | 4 | 1 | 4 | 1 | Ja | [3, 1, 4, 2] | Nein |
+| 3 | 4 | 2 | 4 | 2 | Ja | [3, 1, 2, 4] | Nein |
+| 4 | 4 | - | - | - | - | [3, 1, 2, 4] | Ja (n=3) |
+| 5 | 3 | 0 | 3 | 1 | Ja | [1, 3, 2, 4] | Nein |
+| 6 | 3 | 1 | 3 | 2 | Ja | [1, 2, 3, 4] | Nein |
+| 7 | 3 | - | - | - | - | [1, 2, 3, 4] | Ja (n=2) |
+| 8 | 2 | 0 | 1 | 2 | Nein | [1, 2, 3, 4] | Nein |
+| 9 | 2 | - | - | - | - | [1, 2, 3, 4] | Ja (n=1) |
+==== Detaillierte Analyse des Rekursiven Beispiels ====
+  * **Schritt 1-3**: In der ersten Iteration werden die größten Werte nach rechts verschoben, analog zum nicht-rekursiven Beispiel. Nach diesen Schritten bleibt der größte Wert (4) am Ende des Arrays.
+  * **Schritt 4**: Der erste rekursive Aufruf von ''bubble_sort_recursive'' erfolgt mit ''n = 3''. Dabei werden die nächsten größten Werte sortiert.
+  * **Schritt 5-6**: In dieser rekursiven Iteration werden die Werte weiter sortiert, bis ''3'' und ''2'' an ihrer richtigen Position sind.
+  * **Schritt 7**: Der nächste rekursive Aufruf erfolgt mit ''n = 2''. Da nur noch zwei Elemente überprüft werden, wird die Liste in dieser Iteration vollständig sortiert.
+  * **Schritt 8-9**: Im letzten rekursiven Aufruf mit ''n = 1'' wird keine weitere Aktion mehr ausgeführt, da die Basisbedingung erreicht ist, und der Sortiervorgang ist abgeschlossen.
 ===== Anwendungsfälle von Trace Tables =====