Education
09: Vorlesung | 00:00:07 Sortieren & Co 00:00:07 Formaler 00:06:02 Anwendungsbeispiele 00:07:51 Beispiele aus Kurs/Buch 00:10:48 Überblick 00:12:09 Einfache Sortieralgorithmen 00:15:25 Sentinels am Beispiel Sortieren durch Einfügen 00:16:24 Einfache Sortieralgorithmen 00:18:51 Analyse 00:21:04 Sortieren durch Mischen 00:24:20 Beispiel 00:27:47 Mischen 00:33:29 Untere Schranken 00:35:15 Eine vergleichsbasierte untere Schranke 00:38:31 Baumbasierte Sortierer-Darstellung 00:45:29 Beweis 00:53:18 Randomisierung, Mittlere Ausführungszeit 00:54:02 Quicksort – erster Versuch 00:58:14 Quicksort – Analyse im schlechtesten Fall 01:00:14 Schlechtesten Fall: Beispiel 01:00:59 Quicksort – Analyse im besten Fall 01:03:27 Quicksort – zufälliger Pivot 01:04:51 Satz: Quicksort hat erwartete Laufzeit O(nlogn) 01:06:58 Beweissatz 1: Rekurrenzen 01:20:49 Exkurs: Harmonische Summe