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, 09.01.2018
- Inhalt: Aufgabenstellung; Mergesort
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Mergesort
Vorlesung 17
- Datum: Mittwoch, 10.01.2018
- Inhalt: Schranken fürs Sortieren
- Notizen: HIER
- Weitere Links:
Ein Kapitel von Jeff Erickson über untere Schranken
Wikipedia über Sortierverfahren (mit einem Beweis der unteren Schranke)
Vorlesung 18
- Datum: Donnerstag, 11.01.2018
- Inhalt: Behandeln von Rekursionen
- Notizen: HIER
- Weitere Links:
Recursion (englisch, länger)
Rekursionen (deutsch)
Generating Functions (englisch, länger)
Erzeugende Funktionen (deutsch)
Vorlesung 19
- Datum: Dienstag, 16.01.2018
- Inhalt: Master-Theorem, Weitere Sortieralgorithmen
- Notizen: HIER
- Weitere Links:
Master Theorem (engl.)
Master-Theorem (deutsch)
(Die dort besprochenen Versionen sind spezieller als in der Vorlesung!)
Vorlesung 20
- Datum: Mittwoch, 17.01.2018
- 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
Epic Game of Life (mit epischer Musik, wie gehört)
xkcd #195!
Große Übung 6
- Datum: Donnerstag, 18.01.2018
- Inhalt: Mergesort, Master-Theorem, Bubblesort
- Notizen: HIER
Vorlesung 21
- Datum: Dienstag, 23.01.2018
- Inhalt: Quicksort
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Quicksort
Vorlesung 22
- Datum: Mittwoch, 24.01.2018
- Inhalt: Mediane
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Mediane
Wikipedia über Medianberechnung (englisch, aber lohnend)
Eine sehr detaillierte Darstellung des Median-Agorithmus
Vorlesung 23
- Datum: Dienstag, 30.01.2018
- Inhalt: Sortieren in linearer Zeit, Kapitelzusammenfassung
- Notizen: HIER
- Weitere Links:
Liedtext
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.)