Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
gf_informatik:suchen_und_sortieren:sortieren [2024-03-07 14:20] – [C7 (Herausforderung): Quicksort] hofgf_informatik:suchen_und_sortieren:sortieren [2026-04-09 06:53] (aktuell) – hof
Zeile 41: Zeile 41:
   * Wie gehts du vor?   * Wie gehts du vor?
   * Wieviele Vergleiche sind nötig?   * Wieviele Vergleiche sind nötig?
- 
  
 ### Sortieralgorithmen ### Sortieralgorithmen
Zeile 47: Zeile 46:
 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: 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?   * 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     * Austausch von zwei Elementen
     * Entfernung oder Einfügen eines Elements     * Entfernung oder Einfügen eines Elements
Zeile 68: Zeile 67:
  
 <nodisp 1> <nodisp 1>
- 
 ++++Lösung| ++++Lösung|
-<code python>+<html><script type="module" src="https://bottom.ch/editor/stable/bottom-editor.js"></script></html> 
 +  
 +<html><bottom-editor>
 def is_sorted(l): def is_sorted(l):
     for index in range(len(l) - 1):     for index in range(len(l) - 1):
Zeile 81: Zeile 81:
 print(is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte'])) print(is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte']))
 print(is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel'])) print(is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel']))
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 100: Zeile 100:
  
 Hier dasselbe für [[gf_informatik:suchen_und_sortieren:selection_sort|In-place Selection Sort]]. Hier dasselbe für [[gf_informatik:suchen_und_sortieren:selection_sort|In-place Selection Sort]].
- 
 #### Aufgabe C4: Selection Sort anwenden #### Aufgabe C4: Selection Sort anwenden
 Du hast folgende beiden Listen: Du hast folgende beiden Listen:
Zeile 110: Zeile 109:
  
   - Schreibe eine Funktion ''selection\_sort(li)'', der du eine unsortierte Liste übergeben kannst und die eine sortierte Liste zurückgibt.   - 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.   - 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.    - Erweitere deinen Code, sodass du eine Obstsorte festlegen kannst und am Ende eine der folgenden beiden Nachrichten ausgegeben wird. 
Zeile 118: Zeile 117:
  
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
-<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"] 
  
 +<html><script type="module" src="https://bottom.ch/editor/stable/bottom-editor.js"></script></html>
 +<html><bottom-editor>
 def find_min(l): def find_min(l):
     min_index = 0     min_index = 0
Zeile 154: Zeile 152:
             right = middle - 1             right = middle - 1
     return None     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" mein_obst = "Erdbeere"
Zeile 159: Zeile 160:
 mein_index = binary_search(obstsorten_sortiert, mein_obst) mein_index = binary_search(obstsorten_sortiert, mein_obst)
 if mein_index is None: if mein_index is None:
- print("Die Obstsorte {} wurde nicht gefunden.".format(mein_obst))+ print(f"Die Obstsorte {mein_obst} wurde nicht gefunden.")
 else: 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>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 172: Zeile 173:
 #### C6 (Herausforderung): Laufzeit-Analyse #### C6 (Herausforderung): Laufzeit-Analyse
  
-_Selection Sort_ ist **in-place** (es wird kein zusätzlicher Platz benötigt). +Wie berechnen wir die Laufzeit des Selection-Sort-Algorithmus? Wieviele Vergleiche führen wir bei SelectionSort aus, um `n` Elemente zu sortieren? 
- +  * Um das Minimum zu finden, vergleichen wir das kleinste Element mit allen anderen in der verbleibenden, unsortierten Liste.
-Aber wie berechnen wir die Laufzeit des Algorithmus? Wieviele Vergleiche führen wir bei SelectionSort aus, um `n` Elemente zu sortieren? +
-  * An jeder Position vergleichen wir das Element mit allen folgenden.+
     * Für die Position `0` sind das `n-1` Vergleiche     * Für die Position `0` sind das `n-1` Vergleiche
     * Für die Position `1` sind es `n-2`     * Für die Position `1` sind es `n-2`
     * ...     * ...
     * Für die Position `n-2` ist es ein Vergleich     * 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 $(n-1)/2$ Vergleiche pro Position. +  * Im Durchschnitt sind es also $\frac{n-1}{2}$ Vergleiche pro Position. 
-  * Insgesamt führen wir $n*(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? 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 #### C7 (Herausforderung): Quicksort
  
Zeile 196: Zeile 196:
     * auf jeder Rekursions-Ebene werden `n` Vergleiche getätigt (verteilt auf alle Teillisten).     * auf jeder Rekursions-Ebene werden `n` Vergleiche getätigt (verteilt auf alle Teillisten).
     * wir benötigen ca. $log_2(n)$ Halbierungen, um die Liste in minimale Listen mit nur je einem Element aufzuteilen - diese sind trivialerweise bereits sortiert.     * wir benötigen ca. $log_2(n)$ Halbierungen, um die Liste in minimale Listen mit nur je einem Element aufzuteilen - diese sind trivialerweise bereits sortiert.
-    * damit benötigen wir $n\cdot{}log(n)$ Vergleiche+  * damit benötigen wir $n\cdot{}log(n)$ Vergleiche
  
 Hm, ist $n\cdot{}log(n)$ viel besser als $\frac{n^2}{2}$? [[https://stackoverflow.com/questions/23329234/which-is-better-on-log-n-or-on2|Stackoverflow]] hat die Antwort. Hm, ist $n\cdot{}log(n)$ viel besser als $\frac{n^2}{2}$? [[https://stackoverflow.com/questions/23329234/which-is-better-on-log-n-or-on2|Stackoverflow]] hat die Antwort.
Zeile 217: Zeile 217:
 ++++ ++++
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python quicksort.py> <code python quicksort.py>
Zeile 253: Zeile 253:
  
 def quick_sort(l, links=None, rechts=None): 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.     # Falls die Liste weniger als 2 Elemente hat, ist sie bereits sortiert.
     if links < rechts:     if links < rechts:
  • gf_informatik/suchen_und_sortieren/sortieren.1709821224.txt.gz
  • Zuletzt geändert: 2024-03-07 14:20
  • von hof