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-21 06:54] – [Aufgabe C1: Manuell Sortieren] hofgf_informatik:suchen_und_sortieren:sortieren [2025-03-15 21:18] (aktuell) – [Aufgabe C4: Selection Sort anwenden] hof
Zeile 22: Zeile 22:
  
 Damit wir die effiziente Binärsuche verwenden können, muss der Suchbereich sortiert sein. Aber wie sortieren wir eine Liste? Wie lange dauert es? Damit wir die effiziente Binärsuche verwenden können, muss der Suchbereich sortiert sein. Aber wie sortieren wir eine Liste? Wie lange dauert es?
 +
 #### Aufgabe C1: Manuell Sortieren #### Aufgabe C1: Manuell Sortieren
  
Zeile 53: Zeile 54:
     * 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: Selection Sort+#### 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[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. 
 +++++ 
 + 
 + 
 +<nodisp 1> 
 + 
 +++++Lösung| 
 +<code python> 
 +def is_sorted(l): 
 +    for index in range(len(l) - 1): 
 +        a = l[index] 
 +        b = l[index + 1] 
 +        if b < a: 
 +            return False 
 +    return True 
 + 
 +print(is_sorted(['Apfelküchlein', 'Caramel', 'Zuckerwatte'])) 
 +print(is_sorted(['Zuckerwatte', 'Apfelküchlein', 'Caramel'])) 
 +</code> 
 +++++ 
 +</nodisp> 
 + 
 + 
 +#### Aufgabe C3: Selection Sort
 Das Ziel von _Selection Sort_ ist, zuerst die kleinste Zahl in der Liste zu finden und diese an der ersten Stelle der sortierten Liste zu platzieren. Danach machen wir weiter mit der zweitkleinsten Zahl usw. Das Ziel von _Selection Sort_ ist, zuerst die kleinste Zahl in der Liste zu finden und diese an der ersten Stelle der sortierten Liste zu platzieren. Danach machen wir weiter mit der zweitkleinsten Zahl usw.
  
Zeile 66: Zeile 99:
 Hier ist der [[gf_informatik:suchen_und_sortieren:selection_sort_outplace|Lösungsweg für Selection Sort Schritt für Schritt]] zusammengestellt. Hier ist der [[gf_informatik:suchen_und_sortieren:selection_sort_outplace|Lösungsweg für Selection Sort Schritt für Schritt]] zusammengestellt.
  
-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 C3: Selection Sort anwenden+
 Du hast folgende beiden Listen: Du hast folgende beiden Listen:
 <code python> <code python>
Zeile 133: Zeile 165:
 </nodisp> </nodisp>
  
-#### Zusatzaufgabe: Insertion Sort+#### C5 (Zusatzaufgabe): Insertion Sort
  
 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]].
-#### Herausforderung: Laufzeit-Analyse+#### C6 (Herausforderung): Laufzeit-Analyse
  
-_Selection Sort_ ist **in-place** (es wird kein zusätzlicher Platz benötigt), und stabil (enthält die Liste zwei Elemente mit gleichem Schlüssel, so wird ihre Reihenfolge nicht verändert).+_Selection Sort_ ist **in-place** (es wird kein zusätzlicher Platz benötigt).
  
 Aber wie berechnen wir die Laufzeit des Algorithmus? Wieviele Vergleiche führen wir bei SelectionSort aus, um `n` Elemente zu sortieren? Aber wie berechnen wir die Laufzeit des Algorithmus? Wieviele Vergleiche führen wir bei SelectionSort aus, um `n` Elemente zu sortieren?
Zeile 147: 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?
-#### 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.+#### C7 (Herausforderung): Quicksort 
 + 
 +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 161: 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?
  • gf_informatik/suchen_und_sortieren/sortieren.1708498469.txt.gz
  • Zuletzt geändert: 2024-02-21 06:54
  • von hof