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 [2026/09/01 11:17] (aktuell) – Animation eines zeilenweise entstehenden Trace Tables eingebettet admin
@@ Zeile 16: / Zeile 16: @@
   * **Bedingungen**: Wenn das Programm Kontrollstrukturen wie ''if''-Anweisungen oder Schleifen enthält, werden hier die Bedingungen und ihre Auswertungen dokumentiert.
   * **Kommentare**: Zusätzliche Kommentare oder Erklärungen, die den Ablauf oder besondere Ereignisse im Code verdeutlichen, können hier vermerkt werden.
+===== Animation: eine Trace Table entsteht =====
+In der Animation füllt sich die Tabelle Durchgang für Durchgang, während der Code daneben mitläuft – so, wie Sie sie von Hand schreiben würden. Der erste Tab zeigt eine lineare Suche und macht sichtbar, dass die Schleife nach dem Treffer abbricht und die letzte Zeile gar nie entsteht. Der zweite Tab verfolgt die Collatz-Folge, die zwischendurch grösser wird, bevor sie fällt.
+{{url>https://templates-python.github.io/m323_html/lu01/tracetable.html 100%,860px noborder|Animation: Trace Table Zeile für Zeile}}
 ===== Beispiel eines Trace Tables =====
@@ Zeile 40: / Zeile 46: @@
 | 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 52: @@
   * **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 =====
@@ Zeile 68: / Zeile 114: @@
 ----
-{{tag>M323-LU01}}
+{{tag>M323-LU01 M323-C1B}}
 [[https://creativecommons.org/licenses/by-nc-sa/4.0/ch/|{{https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png}}]] (c) Kevin Maurizi