Lektion 6: Funktionen und Rekursion
Baue das Muster „Sortierwettlauf“ in Python und lerne dabei:
- Funktionen, und eine Funktion als Wert übergeben
- Rekursion: eine Funktion, die sich selbst für kleinere Teile aufruft
- ein Zähler in einem Dictionary
- assert, um ein Ergebnis zu prüfen
- wie der Aufwand wächst: n² gegen n·log n
Erst ansehen
Läuft nach einem Klick von YouTube.
"""Sorting race: four algorithms on the same shuffled list, counting their comparisons.
Run: python sorting-race.py (needs: pip install numpy matplotlib)
"""
import math
import numpy as np
import matplotlib.pyplot as plt
plt.style.use("dark_background")
n = 100
data = list(np.random.default_rng().permutation(n))
count = {"comparisons": 0}
def less(a, b): # every algorithm compares only through this, so we can count
count["comparisons"] += 1
return a < b
def bubble(xs):
xs = xs[:]
for end in range(len(xs) - 1, 0, -1):
for i in range(end):
if less(xs[i + 1], xs[i]):
xs[i], xs[i + 1] = xs[i + 1], xs[i]
return xs
def insertion(xs):
xs = xs[:]
for i in range(1, len(xs)):
j = i
while j > 0 and less(xs[j], xs[j - 1]):
xs[j], xs[j - 1] = xs[j - 1], xs[j]
j -= 1
return xs
def merge(xs):
if len(xs) < 2:
return xs
left, right = merge(xs[: len(xs) // 2]), merge(xs[len(xs) // 2 :])
out = []
while left and right:
out.append(left.pop(0) if not less(right[0], left[0]) else right.pop(0))
return out + left + right
def quick(xs):
if len(xs) < 2:
return xs
pivot, rest = xs[0], xs[1:]
smaller = [x for x in rest if less(x, pivot)]
return quick(smaller) + [pivot] + quick([x for x in rest if x not in smaller])
results = {}
for name, sort in [("bubble", bubble), ("insertion", insertion), ("merge", merge), ("quick", quick)]:
count["comparisons"] = 0
assert sort(data) == sorted(data)
results[name] = count["comparisons"]
print(results, "| at least log2(n!) =", math.ceil(math.log2(math.factorial(n))))
plt.figure(figsize=(7, 4))
plt.bar(list(results), list(results.values()), color=["#f0abfc", "#c4b5fd", "#5eead4", "#5eead4"])
plt.axhline(math.log2(math.factorial(n)), color="white", linestyle="--", label="log2(n!): no comparison sort does better")
plt.ylabel(f"comparisons for n = {n}")
plt.legend()
plt.show()
# Try: n = 1000 (bubble sort needs about n*n/2, merge sort about n*log2(n))
Kein Python auf diesem Computer? Das Notebook führt dasselbe Skript, die Übungen und die Lösungen in deinem Browser aus, in Google Colab. Das Notebook ist auf Englisch.
Zeile für Zeile
def less(a, b):Jeder Algorithmus vergleicht über diese eine Funktion, also lassen sich die Vergleiche an einer Stelle zählen.
count["comparisons"] += 1Ein Dictionary hält den Zähler, damit die Funktion ihn ohne das Schlüsselwort global ändern kann.
def merge(xs):Mergesort: Sortiere jede Hälfte, dann füge die beiden sortierten Hälften zusammen, indem du immer das kleinere vordere Element nimmst.
left, right = merge(xs[: len(xs) // 2]), merge(xs[len(xs) // 2 :])Rekursion: merge ruft sich selbst für jede Hälfte auf, bis ein Teil weniger als zwei Elemente hat.
assert sort(data) == sorted(data)assert hält das Skript an, wenn ein Sortierverfahren die Reihenfolge falsch macht: ein Test, der ins Programm eingebaut ist.
math.ceil(math.log2(math.factorial(n)))Die untere Schranke: log₂ der Zahl der möglichen Reihenfolgen, n!, aufgerundet.
Probier es selbst
Welches Verfahren braucht für n = 100 die wenigsten Vergleiche, und wie nah ist es an der Schranke?
Hinweis
Starte das Skript; es gibt die Zahlen und die Schranke aus.
Lösung
Mergesort, etwa 540 bei einer Schranke von 525. Bubblesort braucht genau 4950, also 100 · 99 ÷ 2.
Warum braucht dieser Bubblesort immer n·(n − 1) ÷ 2 Vergleiche?
Hinweis
Sieh dir seine zwei Schleifen an.
Lösung
Diese Version lässt beide Schleifen immer bis zum Ende laufen: (n − 1) + (n − 2) + … + 1 = n·(n − 1) ÷ 2 Vergleiche, egal in welcher Reihenfolge.
Gib Quicksort eine Liste, die schon sortiert ist. Was passiert mit seiner Zahl?
Hinweis
data = list(range(n)).
Lösung
Sie springt auf 4950, so schlecht wie Bubblesort: Mit dem ersten Element als Pivot lässt jede Teilung eine Seite leer.
Quiz
Lernkarten
Lies die Vorderseite, sag dir die Rückseite vor, dann öffne die Karte.
Rekursion
Eine Funktion, die ein Problem löst, indem sie sich selbst für kleinere Teile davon aufruft.
assert condition
Hält das Programm mit einem Fehler an, wenn die Bedingung False ist.
log₂(n!)
Die wenigsten Ja-Nein-Vergleiche, die n! Reihenfolgen unterscheiden können: die Grenze für jedes vergleichende Sortierverfahren.
n² gegen n·log n
Für 1000 Elemente: etwa 500.000 gegen etwa 10.000 Schritte.
Eine Funktion übergeben
for name, sort in [("merge", merge), …]: Funktionen sind Werte, wie Zahlen.