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 [2025-02-16 09:07] – hofgf_informatik:suchen_und_sortieren:sortieren [2026-02-27 14:19] (aktuell) – hof
Zeile 67: Zeile 67:
  
  
-<nodisp 1>+<nodisp 2>
  
 ++++Lösung| ++++Lösung|
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 184: Zeile 183:
  
 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 197: Zeile 195:
     * 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 218: Zeile 216:
 ++++ ++++
  
-<nodisp 1>+<nodisp 2>
 ++++Lösung| ++++Lösung|
 <code python quicksort.py> <code python quicksort.py>
Zeile 254: Zeile 252:
  
 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.1739696879.txt.gz
  • Zuletzt geändert: 2025-02-16 09:07
  • von hof