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-05-02 14:07] – [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 84: Zeile 83:
 </template> </template>
 <template data-type="test"> <template data-type="test">
-assert is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte']) +assert is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte']) is True 
-assert not is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel'])+assert is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel']) is False
 </template> </template>
 </bottom-exercise> </bottom-exercise>
Zeile 189: 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 222: 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 274: 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.1777730860.txt.gz
  • Zuletzt geändert: 2026-05-02 14:07
  • von hof