Algorithmen I, SS 2015, gehalten am 20.05.2015, Vorlesung 12 (+ Übung)
1 hour 26 minutes Posted Dec 3, 2015 at 3:27 pm.
Prioritätslisten
Prioritätslisten (priority queues)
Prioritätslisten – Anwendungen
Binäre Heaps
Implizite Baum-Repräsentation
Pseudocode
Einfügen
deleteMin: Beispiel
Binärer Heap – Analyse
Binärer Heap – Konstruktion
Beispiel: Binärer Heap – Konstruktion
Binärer Heap – Konstruktion
Ein nützlicher Rechentrick
Heapsort
Heapsort: Beispiel
Heapsort – Quicksort – Mergesort
Adressierbare Prioritätslisten
Adressierbare Prioritätslisten: Anwendungen
Adressierbare Binäre Heaps
Adressierbare Prioritätslisten – Laufzeiten
Prioritätslisten: Mehr
Prioritätslisten: Zusammenfassung
Was haben wir jenseits von Prioritätslisten gelernt?
Übung
Roadmap
Organisation
Sortieren durch Mischen
Merge Sort
Tatsächliche Laufzeit einer Implementierung
Quicksort – erster Versuch
Quicksort – Analyse im schlechtesten Fall
Schlechtester Fall: Beispiel
Einige Quicksort-Analysen
Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen
C++
Java
Dual Pivot Quicksort
Partitionierung mit 2 Pivot
Einige Quicksort-Analysen
Kennzahlen der Vorsortiertet und adaptive Sortierverfahren
Adaptives Sortieren
Runs
Adaptives Sortieren
0:00
1:26:04
Show notes
12: Vorlesung und Übung |Übung
Watch Video
