Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:sortieren [2025-03-11 07:54] – [C7 (Herausforderung): Quicksort] hof
+++ gf_informatik:suchen_und_sortieren:sortieren [2026-05-02 14:12] (aktuell) – [C7 (Herausforderung): Quicksort] hof
@@ Zeile 41: / Zeile 41: @@
   * Wie gehts du vor?
   * Wieviele Vergleiche sind nötig?
 ### Sortieralgorithmen
 Sortieren ist eines der Grundprobleme der Informatik, und es existieren [[http://www.sorting-algorithms.com/|dutzende von Algorithmen]] mit unterschiedlichen Eigenschaften. Die wichtigsten Eigenschaften sind die folgenden:
   * Laufzeit: wieviele Operationen sind nötig, um eine Liste der Länge `n` zu sortieren?
-    * Vergleiche von zwei Elementen
+    * Vergleich von zwei Elementen
     * Austausch von zwei Elementen
     * Entfernung oder Einfügen eines Elements
@@ Zeile 53: / Zeile 51: @@
   * In-Place: Wird abgesehen von der zu sortierenden Liste nur noch eine konstante Speicherkapazität verwendet, oder wird beispielsweise eine neue Liste aufgebaut, die den Speicherbedarf verdoppelt?
     * Wenn du beim Sortieren nur Elemente vertauschst, statt eine neue Liste anzulegen, hast du einen In-Place-Algorithmus verwendet.
 #### Aufgabe C2: Sortierung Prüfen
@@ Zeile 67: / Zeile 66: @@
-<nodisp 1>
+<bottom-exercise id="c2" showsolution>
+<template data-type="starter">
-++++Lösung|
+def is_sorted(l):
-<code python>
+    """Gibt True zurück, falls l sortiert ist, sonst False."""
+</template>
+<template data-type="solution">
 def is_sorted(l):
     for index in range(len(l) - 1):
@@ Zeile 81: / Zeile 82: @@
 print(is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte']))
 print(is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel']))
-</code>
+</template>
-++++
+<template data-type="test">
-</nodisp>
+assert is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte'])
+assert not is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel'])
+</template>
+</bottom-exercise>
@@ Zeile 100: / Zeile 104: @@
 Hier dasselbe für [[gf_informatik:suchen_und_sortieren:selection_sort|In-place Selection Sort]].
 #### Aufgabe C4: Selection Sort anwenden
 Du hast folgende beiden Listen:
 <code python>
 obstsorten = ["Kirsche", "Apfel", "Banane", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"]
@@ Zeile 110: / Zeile 114: @@
   - Schreibe eine Funktion ''selection\_sort(li)'', der du eine unsortierte Liste übergeben kannst und die eine sortierte Liste zurückgibt.
-  - Schreibe danach eine Funktion ''binary\_search(li, el)'', der du eine sortierte Liste und das gesuchte Element übergeben kannst und die den Index des gesuchten Elements in der Liste zurückgibt. Falls die Funktion nichts findet, soll sie None zurückgeben.
+  - Schreibe danach eine Funktion ''binary\_search(li, el)'', der du eine sortierte Liste und das gesuchte Element übergeben kannst und die den Index des gesuchten Elements in der Liste zurückgibt. Falls die Funktion nichts findet, soll sie `None` zurückgeben.
   - Kopiere die beiden Listen in deinen Code.
   - Erweitere deinen Code, sodass du eine Obstsorte festlegen kannst und am Ende eine der folgenden beiden Nachrichten ausgegeben wird.
@@ Zeile 117: / Zeile 121: @@
+<bottom-exercise id="c4" showsolution>
-<nodisp 2>
+<template data-type="starter">
-++++Lösung|
+obstsorten = ["Kirsche", "Apfel", "Banane", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"]
-<code python>
-obstsorten = ["Apfel", "Banane", "Kirsche", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"]
 farben = ["gelb", "rot", "gelb", "grün", "blau", "rot", "rot", "rot", "braun", "orange", "orange", "orange"]
+</template>
+<template data-type="solution">
 def find_min(l):
     min_index = 0
@@ Zeile 154: / Zeile 157: @@
             right = middle - 1
     return None
+obstsorten = ["Apfel", "Banane", "Kirsche", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"]
+farben = ["gelb", "rot", "gelb", "grün", "blau", "rot", "rot", "rot", "braun", "orange", "orange", "orange"]
 mein_obst = "Erdbeere"
@@ Zeile 159: / Zeile 165: @@
 mein_index = binary_search(obstsorten_sortiert, mein_obst)
 if mein_index is None:
-	print("Die Obstsorte {} wurde nicht gefunden.".format(mein_obst))
+	print(f"Die Obstsorte {mein_obst} wurde nicht gefunden.")
 else:
-	print("Die Obstsorte {} hat die Farbe {}.".format(mein_obst, farben[mein_index]))
+	print(f"Die Obstsorte {mein_obst} hat die Farbe {farben[mein_index]}.")
-</code>
+</template>
-++++
+</bottom-exercise>
-</nodisp>
 #### C5 (Zusatzaufgabe): Insertion Sort
 Der Algorithmus wird [[gf_informatik:suchen_und_sortieren:insertion_sort|hier vorgestellt und Schritt für Schritt implementiert]].
-#### C6 (Herausforderung): Laufzeit-Analyse
-_Selection Sort_ ist **in-place** (es wird kein zusätzlicher Platz benötigt).
+#### C6 (Herausforderung): Laufzeit-Analyse
-Aber wie berechnen wir die Laufzeit des Algorithmus? Wieviele Vergleiche führen wir bei SelectionSort aus, um `n` Elemente zu sortieren?
+Wie berechnen wir die Laufzeit des Selection-Sort-Algorithmus? Wieviele Vergleiche führen wir bei SelectionSort aus, um `n` Elemente zu sortieren?
-  * An jeder Position vergleichen wir das Element mit allen folgenden.
+  * Um das Minimum zu finden, vergleichen wir das kleinste Element mit allen anderen in der verbleibenden, unsortierten Liste.
     * Für die Position `0` sind das `n-1` Vergleiche
     * Für die Position `1` sind es `n-2`
     * ...
     * Für die Position `n-2` ist es ein Vergleich
-    * Für die Position `n-1` sind es null Vergleiche
+    * Für die Position `n-1` sind es null Vergleiche (das letzte Element muss nicht mehr verglichen werden)
   * Im Durchschnitt sind es also $\frac{n-1}{2}$ Vergleiche pro Position.
-  * Insgesamt führen wir $\frac{n\cdot(n-1)}{2}$ Vergleiche aus.
+  * Der Schritt wird $n$ Mal ausgeführt, insgesamt benötigen wir $\frac{n\cdot(n-1)}{2}$ Vergleiche.
 Es wird jedes Element mit jedem anderen verglichen. Intuitiv scheint es möglich, mit weniger Vergleichen auszukommen. Wenn wir wissen, dass `x > y` und `y > z` ist, so müssten wir eigentlich `x` nicht mehr mit `z` vergleichen. Aber wieviele Vergleiche sind mindestens notwendig? Können wir einen **Divide & Conquer** Ansatz wie bei der Binärsuche verwenden?
 #### C7 (Herausforderung): Quicksort
@@ Zeile 217: / Zeile 221: @@
 ++++
-<nodisp 1>
+<bottom-exercise id="c7" showsolution>
-++++Lösung|
+<template data-type="starter">
-<code python quicksort.py>
+def teile(l, links, rechts):
+    """
+    Divide-Step von Quicksort: Teilt die angegebene Liste in zwei Teile und gibt
+    den Index des Pivot-Elements zurück.
+    Alle Elemente vor dem Pivot-Element sind <= dem Pivot, alle Elemente nachher sind
+    grösser als der Pivot.
+    """
+def quick_sort(l, links=None, rechts=None):
+    """Sortiert l in-place."""
+</template>
+<template data-type="test">
+assert quick_sort([3, 2, 5, 1]) == [1, 2, 3, 5]
+assert quick_sort([35, 71, 93, 88, 1, 83, 83, 56, 10, 96]) == [1, 10, 35, 56, 71, 83, 83, 88, 93, 96]
+</template>
+<template data-type="solution">
 def teile(l, links, rechts):
     """
@@ Zeile 253: / Zeile 272: @@
 def quick_sort(l, links=None, rechts=None):
-    links = links or 0
+    links = 0 if links is None else links
-    rechts = rechts or len(l) - 1
+    rechts = len(l) - 1 if rechts is None else rechts
     # Falls die Liste weniger als 2 Elemente hat, ist sie bereits sortiert.
     if links < rechts:
@@ Zeile 269: / Zeile 288: @@
 l = [35, 71, 93, 88, 1, 83, 83, 56, 10, 96]
 print(quick_sort(l))
-</code>
+</template>
-++++
+</bottom-exercise>
-</nodisp>