Kapitel 5: Sortieren
Sortieren ist ein grundlegendes algorithmische Problem, das für viele komplexere Aufgaben benötigt wird. Zugleich bieten die zugehörigen Methoden und Prinzipien einen Einstieg in zahlreiche weiterführende Themen.
Vorlesung 16
- Datum: Dienstag, 10.01.2017
- Inhalt: Aufgabenstellung; Mergesort
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Mergesort
Vorlesung 17
- Datum: Mittwoch, 11.01.2017
- Inhalt: Schranken fürs Sortieren; Behandeln von Rekursionen
- Notizen: HIER
- Weitere Links:
Ein Kapitel von Jeff Erickson über untere Schranken
Wikipedia über Sortierverfahren (mit einem Beweis der unteren Schranke)
Große Übung 5
- Datum: Donnerstag, 12.01.2017
- Inhalt: Kombinatorische Probleme; Divide-and-Conquer
- Folien: HIER (Hinweis: Die Multiplikation haben wir leider nicht geschafft; für Interessenten habe ich den Teil mit hochgeladen)
Vorlesung 18
- Datum: Dienstag, 17.01.2017
- Inhalt: Weitere Sortieralgorithmen
- Notizen: HIER
Vorlesung 19
- Datum: Mittwoch, 18.01.2017
- Inhalt: Master-Theorem
- Notizen: HIER
- Weitere Links:
Master Theorem (engl.)
Master-Theorem (deutsch)
(Die dort besprochenen Versionen sind spezieller als in der Vorlesung!)
Vorlesung 20
- Datum: Dienstag, 24.01.2017
- Inhalt: Nichtlineare Rekursionen
- Folien: HIER
- Weitere Links:
Wikipedia über "Die Grenzen des Wachstums"
Diskrete logistische Iterationen
Mehr dazu (mit Animationen) bei Wolfram
The Mandelbrot Set (engl.)
Das gezeigte Mandelbrot-Video
Noch ein Mandelbrot-Video
Und noch ein Mandelbrot-Video
Lineare, nichtlineare Rekursionen, Zahlentheorie und die Mandelbrotmenge
How long is the coast line of Britain?
Wikipedia über Fraktale
Wikipedia on Fractals (engl.)
Life in Life: Game of Life simuliert sich selbst
xkcd #195!
Vorlesung 21
- Datum: Mittwoch, 25.01.2017
- Inhalt: Quicksort
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Quicksort
Große Übung 6
- Datum: Donnerstag, 26.01.2017
- Inhalt: Master-Theorem, Quicksort
- Folien: HIER
Vorlesung 22
- Datum: Dienstag, 31.01.2017
- Inhalt: Mediane
- Notizen: HIER
- Weitere Links:
Wikipedia über Mediane
Vorlesung 23
- Datum: Mittwoch, 01.02.2017
- Inhalt: Laufzeit der Medianberechnung
- Notizen: HIER
- Weitere Links:
Wikipedia über Medianberechnung (englisch, aber lohnend)
Vorlesung 24
- Datum: Dienstag, 07.02.2017
- Inhalt: Sortieren in linearer Zeit
- Notizen: HIER
- Weitere Links:
Visualisierung einiger Sortierverfahren
Roboterduell zwischen Quicksort und Bubblesort
"What's the best way to sort 1 million 32-bit integers?" - Barack Obama antwortet...
Bubblesort als ungarischer Volkstanz
Mergesort als ungarischer Volkstanz
Quicksort als ungarischer Volkstanz (Man beachte, dass die Vertauschungen und Pointerabfolge eine gleichwertige Variation dessen sind, was in der Vorlesung besprochen wurde.)
The Sound of Sorting
The Sound of Quicksort
Maggie Sort: Einsatz von IsNextLargest() im Nachwuchsbereich!
Slowsort (Nicht ganz ernst gemeinte Sortiervariante)
Bogosort
Bogosort (engl.)
Diskussion von Quantum Bogosort (engl.)