Start

Rückblick Vorlesung 16.05

Überblick heutige Vorlesung

Auswahl (Selection)

Beispiel

Auswahl: Anwendungen

Quickselect

Beispiel

Quickselect: Analyse

Mehr zum Auswahlproblem

Durchbrechen der unten Schranke Ganzzahliges Sortieren

Schlüssel 0....k-1: Bucket Sort

Beispiel: k=4

Array-Implementierung

Beispiel

K^d Schlüssel

LSD-Radix-Sort: Beispiel

Mehr zu ganzzahligem Sortieren

Sortieren: vergleichsbasiert vs. ganzzahlig

Was haben wir jeneseits von Sortieren gelernt?

Übung

Roadmap

Rückblick

Sortieren durch Einfügen: In-Place

Sortieren durch Einfügen: Sentinel

Sound

Quantifiziertes Chaos: Inversionen

Quantifiziertes Chaos: Runs

Quantifiziertes Chaos: Removal

Adaptives Sortieren

Insertion Sort: Adaptiv?

Insertion Sort: Erwartete Laufzeit

Natural Merge Sort

Erwartete Anzahl von Runs

Split Sort

Split Sort: Beispiel

Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen

C++

Java