Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- lesson:first [2023/08/13 07:06] – [Eine formale Sortierstrategie] mccab99
+++ lesson:first [2023/08/27 13:44] (aktuell) – Externe Bearbeitung 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-===== Was ist Informatik eigentlich? =====
+===== Über Algorithmen =====
 <WRAP center round info 95%>
@@ Zeile 86: / Zeile 86: @@
 <file python bubblesort.py>
+def bubbleSort(arr):
+    # Anzahl der Zahlen ermitteln
+    n = len(arr)
+    # Erstmal nehmen wir an, dass keine Vertauschungen notwendig waren
+    swapped = False
+    # Jetzt nehmen wir uns jede Zahl vor und vergleichen sie mit ihrer Nachbarzahl
+    for i in range(n-1):
+        # "for" ist eine Schleife, die (n-1)-mal läuft
+        # i ist ein Zähler und erhöht sich bei jedem Durchlauf um 1
+        # die letzte Zahl lassen wir beim Vergleich aus
+        # wir gehen nur bis zur vorletzten (n-1)
+        # das sind praktisch die "Durchläufe"
+        for j in range(0, n-i-1):
+            # bei jedem Durchlauf müssen wir Schritt für Schritt durch die
+            # noch nicht geprüften Zahlen gehen
+            # Durchlauf 1 - Schritt 1, Durchlauf 1 - Schritt 2 usw.
+            if arr[j] > arr[j + 1]:
+                swapped = True
+                arr[j], arr[j + 1] = arr[j + 1], arr[j]
+        if not swapped:
+            # wenn wir nichts tauschen mussten, sind wir fertig
+            return
+# Zahlen, die zu sortieren sind
+arr = [64, 34, 25, 12, 22, 11, 90]
+bubbleSort(arr)
+print("Ausgabe der sortierten Zahlen:")
+for i in range(len(arr)):
+    print("% d" % arr[i], end=" ")
 </file>
 ++++
@@ Zeile 166: / Zeile 199: @@
   - Schreibe die Abfolge der Durchläufe in der kurzen Schreibweise für diese Zahlenreihe auf.
   - Vergleiche zwischendurch immer mal wieder mit den Lösungen deiner Nachbarn.
+  - [[loesung:bubblesort|Lösung]]
 </WRAP>
@@ Zeile 177: / Zeile 211: @@
   * Was sagt dein Gefühl über die Anzahl der Vergleiche, die für die Sortierung benötigt werden, im Unterschied zu Bubblesort?
+++++Auflösung |
+Das Aufwändige für einen Rechner sind Vergleiche. Im Prinzip muss man für einen Vergleich eine Subtraktion durchführen und dann zwei Fälle unterscheiden:
+  - Ist das Ergebnis 0, dann sind die Zahlen gleich
+  - Ist das Ergebnis von 0 verschieden, dann sind die Zahlen nicht gleich
+Ein Tausch von Zahlen ist dagegen vergleichweise einfach - es wird intern nur ein Zeiger umgestellt. [[loesung:bubblesort|Bei Bubblesort hast du gesehen]], dass für die gegebene Zahlenreihe 40 Vergleiche notwendig sind, um den Algorithmus abzuschließen.
+Quicksort ist etwas schwieriger syntaktisch aufzuschreiben, aber wir schauen mal.
+  * das aktuelle Pivotelement ist **fett** formatiert.
+  * eine unterstrichene Zahl ist ein Zahl, die mit dem Pivot-Element verglichen wurde
+  * die Anzahl der unterstrichenen Zahlen ist also die Gesamtzahl der Vergleiche im aktuellen Durchgang
+**Durchgang 1 - 6 ist Pivotelement:**\\
+__3__ __7__ 1 8 2 5 9 __4__ **6**\\
+//4// 1 8 2 5 9 //7// **6** ( 4 und 7 wurden getauscht)\\
+4 __1__ __8__ 2 __5__ __9__ 7 **6**\\
+4 1 //5// 2 //8// 9 7 **6**( 5 und 8 wurden getauscht)\\
+[ 3 4 1 5 2 ] //6// [ 9 7 //8// ] ( 6 und 8 wurden getauscht, Vergleich war unnötig, die 6 muss die kleinste Zahl sein)\\
+Wir haben in diesem ersten Durchgang insgesamt 7x Zahlen miteinander verglichen. Die 6 liegt jetzt schon auf ihrer Endposition.
+Wir werden weiterhin ...
+  * für das Pivot-Element **2** 3x vergleichen müssen
+  * für das Pivot-Element **4** 2x vergleichen müssen
+  * für das Pivot-Element **8** 1x vergleichen müssen
+Wir kommen also mit 13 Vergleichen aus. Quicksort ist um Größenordnungen effizienter als Bubblesort. Bei einer bereits sortierten Liste (Best-Case) bringt Quicksort keinen Nachteil gegenüber Bubblesort.
+++++
 ===== Ja, und was ist jetzt mit Informatik? =====
 Für eine ganz präzise Formulierung ist es jetzt noch zu früh, aber du hast unglaublich wichtige Grundprinzipien eines //Teilbereichs der Informatik// (algorithmisches Problemlösen) kennen gelernt: