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 [2026-03-10 08:11] – [Aufgabe C4: Selection Sort anwenden] hofgf_informatik:suchen_und_sortieren:sortieren [2026-06-09 05:28] (aktuell) – [Sortieralgorithmen] hof
Zeile 22: Zeile 22:
  
 Damit wir die effiziente Binärsuche verwenden können, muss der Suchbereich sortiert sein. Aber wie sortieren wir eine Liste? Wie lange dauert es? Damit wir die effiziente Binärsuche verwenden können, muss der Suchbereich sortiert sein. Aber wie sortieren wir eine Liste? Wie lange dauert es?
- 
 #### Aufgabe C1: Manuell Sortieren #### Aufgabe C1: Manuell Sortieren
  
Zeile 41: Zeile 40:
   * Wie gehts du vor?   * Wie gehts du vor?
   * Wieviele Vergleiche sind nötig?   * Wieviele Vergleiche sind nötig?
- 
 ### Sortieralgorithmen ### Sortieralgorithmen
  
Zeile 52: Zeile 50:
   * 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?   * 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.     * Wenn du beim Sortieren nur Elemente vertauschst, statt eine neue Liste anzulegen, hast du einen In-Place-Algorithmus verwendet.
 +
  
 #### Aufgabe C2: Sortierung Prüfen #### Aufgabe C2: Sortierung Prüfen
Zeile 66: Zeile 65:
  
  
-<nodisp 1> +<bottom-exercise id="c2" showsolution> 
-++++Lösung| +<template data-type="starter"> 
-<html><script type="module" src="https://bottom.ch/ksr/ed/bottom-editor.js"></script></html> +def is_sorted(l): 
-  +    """Gibt True zurück, falls l sortiert ist, sonst False.""" 
-<html><bottom-editor>+</template> 
 +<template data-type="solution">
 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']))
-</bottom-editor></html> +</template> 
-++++ +<template data-type="test"> 
-</nodisp>+assert is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte']) is True 
 +assert is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel']) is False 
 +</template> 
 +</bottom-exercise>
  
  
Zeile 102: Zeile 105:
 #### Aufgabe C4: Selection Sort anwenden #### Aufgabe C4: Selection Sort anwenden
 Du hast folgende beiden Listen: Du hast folgende beiden Listen:
 +
 <code python> <code python>
 obstsorten = ["Kirsche", "Apfel", "Banane", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"] obstsorten = ["Kirsche", "Apfel", "Banane", "Orange", "Mango", "Pfirsich", "Erdbeere", "Birne", "Himbeere", "Kiwi", "Ananas", "Blaubeere"]
Zeile 116: Zeile 120:
  
  
- +<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"] farben = ["gelb", "rot", "gelb", "grün", "blau", "rot", "rot", "rot", "braun", "orange", "orange", "orange"]
 +</template> 
 +<template data-type="solution">
 def find_min(l): def find_min(l):
     min_index = 0     min_index = 0
Zeile 153: Zeile 156:
             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 158: Zeile 164:
 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> +</template> 
-++++ +</bottom-exercise> 
-</nodisp>+
  
 #### C5 (Zusatzaufgabe): Insertion Sort #### C5 (Zusatzaufgabe): Insertion Sort
Zeile 182: Zeile 188:
  
 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 215: Zeile 220:
 ++++ ++++
  
-<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): def teile(l, links, rechts):
     """     """
Zeile 267: Zeile 287:
 l = [35, 71, 93, 88, 1, 83, 83, 56, 10, 96] l = [35, 71, 93, 88, 1, 83, 83, 56, 10, 96]
 print(quick_sort(l)) print(quick_sort(l))
-</code> +</template> 
-++++ +</bottom-exercise> 
-</nodisp>+
  • gf_informatik/suchen_und_sortieren/sortieren.1773130275.txt.gz
  • Zuletzt geändert: 2026-03-10 08:11
  • von hof