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-04-09 06:53] – hofgf_informatik:suchen_und_sortieren:sortieren [2026-05-02 14:12] (aktuell) – [C7 (Herausforderung): Quicksort] 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 52: 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?   * 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 66:
  
  
-<nodisp 1> +<bottom-exercise id="c2" showsolution> 
-++++Lösung| +<template data-type="starter"> 
-<html><script type="module" src="https://bottom.ch/editor/stable/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 82:
 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']) 
 +assert not is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel']) 
 +</template> 
 +</bottom-exercise>
  
  
Zeile 102: Zeile 106:
 #### 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 121:
  
  
- +<bottom-exercise id="c4" showsolution> 
-<nodisp 1> +<template data-type="starter"> 
-++++Lösung| +obstsorten = ["Kirsche", "Apfel", "Banane", "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> +</template> 
-<html><bottom-editor>+<template data-type="solution">
 def find_min(l): def find_min(l):
     min_index = 0     min_index = 0
Zeile 163: Zeile 168:
 else: else:
  print(f"Die Obstsorte {mein_obst} hat die Farbe {farben[mein_index]}.")  print(f"Die Obstsorte {mein_obst} hat die Farbe {farben[mein_index]}.")
-</bottom-editor></html> +</template> 
-++++ +</bottom-exercise> 
-</nodisp>+
  
 #### C5 (Zusatzaufgabe): Insertion Sort #### C5 (Zusatzaufgabe): Insertion Sort
Zeile 184: Zeile 189:
  
 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 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): def teile(l, links, rechts):
     """     """
Zeile 269: Zeile 288:
 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.1775717631.txt.gz
  • Zuletzt geändert: 2026-04-09 06:53
  • von hof