Sortierverfahren | MathePrisma

Für die Aufwandsanalyse orientieren wir uns am C-Programm.

Schlüsselvergleiche: Die Berechnung der Schlüsselvergleiche ist wegen der rekursiven Aufrufe komplizierter.
Deswegen seien nur die Ergebnisse angegeben.

Der schlechteste Fall tritt auf, wenn die Folge absteigend sortiert ist.

$V_{max}(n) = \frac{n^2}{8} + \mathcal{O}(n)$

Im Mittel werden nicht wesentlich mehr Schlüsselvergleiche benötigt als im besten Fall.

$\begin{array}{lll} V_{min}(n) & = & \mathcal{O}(n \cdot \log(n))\\ &&\\ V_{mid}(n) & \leq & 3n \cdot \log(n) \end{array}$

Umspeicherungen:

Da die Anzahl der Umspeicherungen höchstens so groß ist wie die Anzahl der Schlüsselvergleiche, folgt:

$\begin{array}{lll} U_{min}(n) & = & \mathcal{O}(n \cdot \log(n)) \\ &&\\ U_{max}(n) & = & \mathcal{O}(n^2) \\ &&\\ U_{mid}(n) & = & \mathcal{O}(n \cdot \log(n)) \end{array}$

Quicksort ist am schnellsten

Quicksort erreicht damit im Mittel den geringsten Aufwand unter allen betrachteten Verfahren. Man kann sogar zeigen, dass es wesentlich schnellere Verfahren gar nicht geben kann.

a)	Testen Sie, wie viele Schüsselvergleiche und wie viele Umspeicherungen die verschiedenen Verfahren durchführen, wenn die Werte anfangs aufsteigend bzw. absteigend sortiert sind.
b)	Vergleichen Sie die ermittelten Werte mit den Aufwandsabschätzungen.

a)
b)
c)	Wie viele Umspeicherungen benötigt man insgesamt bei den vier Sortierverfahren, um die Schlüssel aufsteigend zu sortieren.