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 [2025-03-15 21:18] (aktuell) – [Aufgabe C4: Selection Sort anwenden] hof
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 118: Zeile 117:
  
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python> <code python>
Zeile 169: Zeile 168:
  
 Der Algorithmus wird [[gf_informatik:suchen_und_sortieren:insertion_sort|hier vorgestellt und Schritt für Schritt implementiert]]. Der Algorithmus wird [[gf_informatik:suchen_und_sortieren:insertion_sort|hier vorgestellt und Schritt für Schritt implementiert]].
- 
 #### C6 (Herausforderung): Laufzeit-Analyse #### C6 (Herausforderung): Laufzeit-Analyse
  
Zeile 181: Zeile 179:
     * 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
-  * 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.+  * Insgesamt führen wir $\frac{n\cdot(n-1)}{2}$ Vergleiche aus.
  
 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 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. log2(n) Halbierungen, um die Liste in minimale Listen mit nur je einem Element aufzuteilen - diese sind trivialerweise bereits sortiert.     * wir benötigen ca. log2(n) Halbierungen, um die Liste in minimale Listen mit nur je einem Element aufzuteilen - diese sind trivialerweise bereits sortiert.
-    * damit benötigen wir n⋅log(n) Vergleiche+  * damit benötigen wir n⋅log(n) Vergleiche
  
 Hm, ist n⋅log(n) viel besser als n22? [[https://stackoverflow.com/questions/23329234/which-is-better-on-log-n-or-on2|Stackoverflow]] hat die Antwort. Hm, ist n⋅log(n) viel besser als n22? [[https://stackoverflow.com/questions/23329234/which-is-better-on-log-n-or-on2|Stackoverflow]] hat die Antwort.
Zeile 217: Zeile 216:
 ++++ ++++
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python quicksort.py> <code python quicksort.py>
  • gf_informatik/suchen_und_sortieren/sortieren.1709821224.txt.gz
  • Zuletzt geändert: 2024-03-07 14:20
  • von hof