Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:sortieren [2024-03-05 08:19] – [Aufgabe C2: Sortierung Prüfen] hof
+++ gf_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]].
 #### Aufgabe C4: Selection Sort anwenden
 Du hast folgende beiden Listen:
@@ Zeile 118: / Zeile 117: @@
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
 <code python>
@@ Zeile 169: / Zeile 168: @@
 Der Algorithmus wird [[gf_informatik:suchen_und_sortieren:insertion_sort|hier vorgestellt und Schritt für Schritt implementiert]].
 #### C6 (Herausforderung): Laufzeit-Analyse
@@ Zeile 181: / Zeile 179: @@
     * Für die Position `n-2` ist es ein Vergleich
     * 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?
@@ Zeile 188: / Zeile 186: @@
 #### C7 (Herausforderung): Quicksort
-Von der Binärsuche wissen wir, dass wir eine Liste in $log2(n)$ Halbierungen auf einzelne Elemente reduzieren können. Hätten wir nun eine Möglichkeit, beim Halbieren auch noch sicherzustellen, dass die beiden Hälften entmischt sind (also, dass alle Elemente in der ersten Hälfte kleiner sind als die Elemente in der zweiten Hälfte), so hätten wir schon fast gewonnen.
+Von der Binärsuche wissen wir, dass wir eine Liste in $log_2(n)$ Halbierungen auf einzelne Elemente reduzieren können. Hätten wir nun eine Möglichkeit, beim Halbieren auch noch sicherzustellen, dass die beiden Hälften entmischt sind (also, dass alle Elemente in der ersten Hälfte kleiner sind als die Elemente in der zweiten Hälfte), so hätten wir schon fast gewonnen.
   * 1. Die ganze Liste in zwei Teile teilen:
@@ Zeile 196: / Zeile 194: @@
   * 2. Schritt 1 rekursiv wiederholen für die beiden Teil-Listen `[links,mitte-1]` und `[mitte+1,rechts]`
     * 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. $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*log(n)$ Vergleiche
+  * damit benötigen wir $n\cdot{}log(n)$ Vergleiche
-Hm, ist $n*log(n)$ viel besser als $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.
 Das obige Rezept beschreibt den [[wpde>Quicksort]] Algorithmus. Getraust du dich an eine Implementierung in Python?
@@ Zeile 218: / Zeile 216: @@
 ++++
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
 <code python quicksort.py>