Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:sortieren [2024-02-28 10:18] – hof
+++ gf_informatik:suchen_und_sortieren:sortieren [2025-03-15 21:18] (aktuell) – [Aufgabe C4: Selection Sort anwenden] hof
@@ Zeile 41: / Zeile 41: @@
   * Wie gehts du vor?
   * Wieviele Vergleiche sind nötig?
 ### Sortieralgorithmen
@@ Zeile 52: / Zeile 53: @@
   * In-Place: Wird abgesehen von der zu sortierenden Liste nur noch eine konstante Speicherkapazität verwendet, oder wird beispielsweise eine neue Liste aufgebaut, die den Speicherbedarf verdoppelt?
     * Wenn du beim Sortieren nur Elemente vertauschst, statt eine neue Liste anzulegen, hast du einen In-Place-Algorithmus verwendet.
 #### Aufgabe C2: Sortierung Prüfen
 Schreibe eine Funktion `is_sorted(l)` die genau dann `True` zurückgibt, wenn `l` aufsteigend sortiert ist, sonst `False`.
+Wieviele Vergleiche sind nötig, um eine Liste der Länge $n$ zu testen?
 ++++Hinweise|
-  * Wir müssen alle nebeneinander liegenden Paare `a = l[i]` und `b = l[i+1]` durchgehen.
+  * Wir müssen alle nebeneinander liegenden Paare `a = l[index]` und `b = l[index+1]` durchgehen.
+    * Dabei müssen wir aufpassen, dass wir mit `index+1` nicht über das Ende der Liste hinaus lesen.
   * Wenn wir ein Paar finden, für das nicht `a <= b` gilt, so ist die Liste nicht aufsteigend sortiert.
   * Wenn wir kein Paar finden (also alle Paare durchprobiert haben), so ist die Liste sortiert.
@@ Zeile 64: / Zeile 67: @@
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
@@ Zeile 97: / 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 115: / Zeile 117: @@
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
 <code python>
@@ Zeile 166: / 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 178: / 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 185: / 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 193: / 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 215: / Zeile 216: @@
 ++++
-<nodisp 2>
+<nodisp 1>
 ++++Lösung|
 <code python quicksort.py>