10: Algorithmen 1, Vorlesung und Übung, SS 2018, 23.05.2018

0:00:00 Start
0:00:40 Rückblick Vorlesung 16.05
0:01:07 Überblick heutige Vorlesung
0:03:48 Auswahl (Selection)
0:06:36 Beispiel
0:08:29 Auswahl: Anwendungen
0:10:08 Quickselect
0:14:16 Beispiel
0:17:01 Quickselect: Analyse
0:18:03 Mehr zum Auswahlproblem
0:21:41 Durchbrechen der unten Schranke - Ganzzahliges Sortieren
0:25:17 Schlüssel 0....k-1: Bucket Sort
0:28:49 Beispiel: k=4
0:30:46 Array-Implementierung
0:31:13 Beispiel
0:35:37 K^d Schlüssel
0:41:49 LSD-Radix-Sort: Beispiel
0:41:56 Mehr zu ganzzahligem Sortieren
0:42:10 Sortieren: vergleichsbasiert vs. ganzzahlig
0:43:48 Was haben wir jeneseits von Sortieren gelernt?
0:45:52 Übung
0:46:19 Roadmap
0:47:23 Rückblick
0:49:00 Sortieren durch Einfügen: In-Place
0:50:11 Sortieren durch Einfügen: Sentinel
0:51:52 Sound
0:55:34 Quantifiziertes Chaos: Inversionen
0:58:22 Quantifiziertes Chaos: Runs
0:59:42 Quantifiziertes Chaos: Removal
1:00:26 Adaptives Sortieren
1:01:21 Insertion Sort: Adaptiv?
1:02:12 Insertion Sort: Erwartete Laufzeit
1:06:36 Natural Merge Sort
1:07:58 Erwartete Anzahl von Runs
1:16:55 Split Sort
1:18:49 Split Sort: Beispiel
1:22:09 Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen
... mehr1:23:18 C++
1:24:23 Java