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-02-28 10:23] – [Aufgabe C2: Sortierung Prüfen] hofgf_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?   * Wie gehts du vor?
   * Wieviele Vergleiche sind nötig?   * Wieviele Vergleiche sind nötig?
 +
  
 ### Sortieralgorithmen ### 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?   * 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.     * Wenn du beim Sortieren nur Elemente vertauschst, statt eine neue Liste anzulegen, hast du einen In-Place-Algorithmus verwendet.
 +
 #### Aufgabe C2: Sortierung Prüfen #### Aufgabe C2: Sortierung Prüfen
 Schreibe eine Funktion `is_sorted(l)` die genau dann `True` zurückgibt, wenn `l` aufsteigend sortiert ist, sonst `False`. Schreibe eine Funktion `is_sorted(l)` die genau dann `True` zurückgibt, wenn `l` aufsteigend sortiert ist, sonst `False`.
Zeile 65: Zeile 67:
  
  
-<nodisp 2>+<nodisp 1>
  
 ++++Lösung| ++++Lösung|
Zeile 98: 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 116: Zeile 117:
  
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python> <code python>
Zeile 167: 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 179: 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?
Zeile 186: Zeile 186:
 #### C7 (Herausforderung): Quicksort #### 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:   * 1. Die ganze Liste in zwei Teile teilen:
Zeile 194: Zeile 194:
   * 2. Schritt 1 rekursiv wiederholen für die beiden Teil-Listen `[links,mitte-1]` und `[mitte+1,rechts]`   * 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).     * 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? Das obige Rezept beschreibt den [[wpde>Quicksort]] Algorithmus. Getraust du dich an eine Implementierung in Python?
Zeile 216: Zeile 216:
 ++++ ++++
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python quicksort.py> <code python quicksort.py>
  • gf_informatik/suchen_und_sortieren/sortieren.1709115809.txt.gz
  • Zuletzt geändert: 2024-02-28 10:23
  • von hof