Starten

Erinnerung VL vom 18.05.2016

Nachtrag zur unteren Schranke: Randomisierung, Mittlere Ausführungszeit

Erinnerung: Mergesort

Quicksort erster Versuch

Quicksort Analyse im schlechtesten Fall

Quicksort Analyse im besten Fall

Quicksort zufälliger Pivot

Satz: Quicksort hat erwartete Laufzeit 0( nlog n )

Beweisansatz 1: Rekurrenzen

Exkurs: Harmonische Summe

Quicksort: Effiziente Implementierung

Beispiel: Partitionierung, k=1

Größerer Basisfall

Halbrekursive Implementierung