Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:sortieren [2025-02-16 09:07] – 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 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?
 #### C7 (Herausforderung): Quicksort
@@ Zeile 197: / Zeile 195: @@
     * 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.
-    * 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.