Sortieren, Rekursion und Beweise
"Sortierstrategien vergleichen und rekursive Probleme verkleinern."
Konzepte verständlich erklärt (für Einsteiger jeden Alters)
Lernziele
Sortierstrategien vergleichen und rekursive Probleme verkleinern. Nach dieser Lektion kannst du das Konzept erklären, ein kleines Beispiel umsetzen und typische Grenzen benennen.
Erklärung
Bubble Sort tauscht benachbarte Fehlpaare; Selection Sort wählt wiederholt das Minimum. Merge Sort teilt die Eingabe, sortiert Teilfolgen und mischt sie in O(n log n). Rekursion löst einen kleineren Fall und braucht einen Basisfall.
Schrittweises Beispiel
Merge Sort auf [7, 2, 5, 1]: teile in [7,2] und [5,1], sortiere zu [2,7] und [1,5], mische zu [1,2,5,7].
def halves(n):
if n <= 1:
return 1
return 1 + halves(n // 2)
print(halves(16))
Zusammenfassung
Teile-und-herrsche kann Laufzeit verbessern, kostet aber oft zusätzlichen Speicher.
Lerncheck & Übung
Etwa 35 Minuten · intermediate
Das lernst du
- Erkläre die Kernidee von „Sortieren, Rekursion und Beweise“ in eigenen Worten.
- Wähle eine passende Technik für einen konkreten Anwendungsfall.
- Erkenne mindestens eine typische Fehlerquelle.
Voraussetzungen
- Keine Zugriffsvoraussetzungen. Vorwissen wird in der Erklärung eingeführt.
Häufige Fehler
- Ohne Basisfall endet Rekursion nicht. Ein Sortiervergleich zählt nicht automatisch Speicherbedarf oder Stabilität mit.
Wissenscheck
Praktische Aufgabe
Zähle rekursive Aufrufe für eine Halbierung von 16 bis 1 und gib die Anzahl aus.
Quellen und Einordnung
Prüfe meine Erklärung zu „Sortieren, Rekursion und Beweise“: Nenne eine fehlende Annahme und stelle mir eine Gegenfrage.
Interaktive Übung & lokaler Testlauf
Zähle rekursive Aufrufe für eine Halbierung von 16 bis 1 und gib die Anzahl aus.
Hinweise auf Wunsch anzeigen
- Zerlege die Aufgabe in Eingabe, Verarbeitung und erwartete Ausgabe.
- Prüfe auch einen leeren oder ungültigen Fall.