Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| gf_informatik:suchen_und_sortieren:sortieren [2024-02-27 23:03] – [Sortieralgorithmen] 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? | * Wie gehts du vor? | ||
| * Wieviele Vergleiche sind nötig? | * Wieviele Vergleiche sind nötig? | ||
| + | |||
| ### Sortieralgorithmen | ### Sortieralgorithmen | ||
| Zeile 53: | Zeile 54: | ||
| * Wenn du beim Sortieren nur Elemente vertauschst, | * Wenn du beim Sortieren nur Elemente vertauschst, | ||
| - | + | #### Aufgabe | |
| - | #### Aufgabe | + | |
| Schreibe eine Funktion `is_sorted(l)` die genau dann `True` zurückgibt, | Schreibe eine Funktion `is_sorted(l)` die genau dann `True` zurückgibt, | ||
| + | |||
| + | Wieviele Vergleiche sind nötig, um eine Liste der Länge $n$ zu testen? | ||
| ++++Hinweise| | ++++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 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. | * Wenn wir kein Paar finden (also alle Paare durchprobiert haben), so ist die Liste sortiert. | ||
| Zeile 64: | Zeile 67: | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| Zeile 83: | Zeile 86: | ||
| - | #### Aufgabe | + | #### Aufgabe |
| 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 97: | Zeile 100: | ||
| Hier dasselbe für [[gf_informatik: | Hier dasselbe für [[gf_informatik: | ||
| - | + | #### Aufgabe | |
| - | #### Aufgabe | + | |
| Du hast folgende beiden Listen: | Du hast folgende beiden Listen: | ||
| <code python> | <code python> | ||
| Zeile 163: | Zeile 165: | ||
| </ | </ | ||
| - | #### C4 (Zusatzaufgabe): | + | #### C5 (Zusatzaufgabe): |
| Der Algorithmus wird [[gf_informatik: | Der Algorithmus wird [[gf_informatik: | ||
| + | #### C6 (Herausforderung): | ||
| - | #### C5 (Herausforderung): | + | _Selection Sort_ ist **in-place** (es wird kein zusätzlicher Platz benötigt). |
| - | + | ||
| - | _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). | + | |
| Aber wie berechnen wir die Laufzeit des Algorithmus? | Aber wie berechnen wir die Laufzeit des Algorithmus? | ||
| Zeile 178: | 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? | ||
| - | #### C6 (Herausforderung): | + | #### C7 (Herausforderung): |
| - | 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, | + | 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, |
| * 1. Die ganze Liste in zwei Teile teilen: | * 1. Die ganze Liste in zwei Teile teilen: | ||
| Zeile 193: | Zeile 194: | ||
| * 2. Schritt 1 rekursiv wiederholen für die beiden Teil-Listen `[links, | * 2. Schritt 1 rekursiv wiederholen für die beiden Teil-Listen `[links, | ||
| * 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, | + | * wir benötigen ca. $log_2(n)$ Halbierungen, |
| - | * 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:// | + | Hm, ist $n\cdot{}log(n)$ viel besser als $\frac{n^2}{2}$? [[https:// |
| Das obige Rezept beschreibt den [[wpde> | Das obige Rezept beschreibt den [[wpde> | ||
hof