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-03-07 14:20] – [C7 (Herausforderung): Quicksort] hof | gf_informatik:suchen_und_sortieren:sortieren [2026-02-27 14:19] (aktuell) – hof | ||
|---|---|---|---|
| Zeile 67: | Zeile 67: | ||
| - | < | + | < |
| ++++Lösung| | ++++Lösung| | ||
| Zeile 100: | Zeile 100: | ||
| Hier dasselbe für [[gf_informatik: | Hier dasselbe für [[gf_informatik: | ||
| - | |||
| #### Aufgabe C4: Selection Sort anwenden | #### Aufgabe C4: Selection Sort anwenden | ||
| Du hast folgende beiden Listen: | Du hast folgende beiden Listen: | ||
| Zeile 169: | Zeile 168: | ||
| Der Algorithmus wird [[gf_informatik: | Der Algorithmus wird [[gf_informatik: | ||
| - | |||
| #### C6 (Herausforderung): | #### C6 (Herausforderung): | ||
| Zeile 181: | 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? | ||
| + | |||
| #### C7 (Herausforderung): | #### C7 (Herausforderung): | ||
| Zeile 196: | Zeile 195: | ||
| * 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. $log_2(n)$ Halbierungen, | * wir benötigen ca. $log_2(n)$ Halbierungen, | ||
| - | | + | |
| Hm, ist $n\cdot{}log(n)$ viel besser als $\frac{n^2}{2}$? | Hm, ist $n\cdot{}log(n)$ viel besser als $\frac{n^2}{2}$? | ||
| Zeile 253: | Zeile 252: | ||
| def quick_sort(l, | def quick_sort(l, | ||
| - | links = links or 0 | + | links = 0 if links is None else links |
| - | rechts = rechts or len(l) - 1 | + | rechts = len(l) - 1 if rechts is None else rechts |
| # Falls die Liste weniger als 2 Elemente hat, ist sie bereits sortiert. | # Falls die Liste weniger als 2 Elemente hat, ist sie bereits sortiert. | ||
| if links < rechts: | if links < rechts: | ||
hof