KIT | KIT-Bibliothek | Impressum | Datenschutz

09: Algorithmen 1, Vorlesung, SS 2017, 24.05.2017

Müller-Quade, Jörn; Witt, Sascha; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:13 Quicksort-zufälliger Pivot
  • 0:05:32 Satz: Quicksort hat erwartete Laufzeit
  • 0:20:42 Exkurs: Harmonische Summe
  • 0:27:19 Quicksort: Effiziente Implementierung
  • 0:38:01 Beispiel: Partinonierung
  • 0:41:31 Beispiel: Rekursion
  • 0:43:42 Größerer Basisfall
  • 0:45:48 Inplace? Wirklich?
  • 0:47:33 Halbrekursive Implementierung
  • 0:50:15 Quadratische Komplexität bei gleichen Elementen?
  • 0:50:52 Anfang der Übung
  • 0:54:07 Rückblick: Insertion Sort
  • 0:57:36 Sentinels am Beispiel Sortieren durch Einfügen
  • 1:04:01 adaptives Sortieren
  • 1:08:04 Insertion Sort: Adaptiv?
  • 1:10:13 Insertion Sort: Erwartete Laufzeit
  • 1:14:15 Natural Merge Sort
  • 1:14:54 Runs
  • 1:21:23 Zusammenfassung: Adaptives Sortieren
  • 1:22:17 Beispiel: C++
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 29.05.2017
Erstellungsdatum 24.05.2017
DOI 10.5445/DIVA/2017-280
Identifikator KITopen-ID: 1000114682
Lizenz KITopen-Lizenz
Serie Algorithmen I, Vorlesung, SS 2017
Folge 9
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page