Starten

Rückblick: Sortieren & Co

Überblick

Einfache Sortieralgorithmen

Sentinels am Beispiel Sortieren durch Einfügen

Analyse

Sortieren durch Mischen

Beispiel

Mischen

Analyse

Sortieren durch Mischen

Untere Schranken

Eine vergleichsbasierte untere Schranke

Baumbasierte Sortierer-Darstellung

Beweis

Übung 5

Roadmap

Rückblick: Insertion Sort

Sentinels am Beispiel Sortieren durch Einfügen

Anschaulich...(Rumänischer Volkstanz)

Adaptives Sortieren

Insertion Sort

Insertion Sort Average Case

Natural Merge Sort

Runs

Removals

Split Sort

Adaptives Sortieren (Zusammenfassung)

Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen

C++

Java