Sortierverfahren | MathePrisma

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

Die i-Schleife wird (n-1)-mal durchlaufen.
Beim i-ten Durchlauf wird die j-Schleife (n - (i+1)) = (n-i-1)-mal durchlaufen.
Dabei erfolgt jeweils ein Schlüsselvergleich.

Die Gesamtzahl der Schlüsselvergleiche ist also unabhängig von den Schlüsseln der Datensätze:

$\begin{array}{lll} V_{min}(n) & = & V_{mid}(n) = V_{max}(n)\\ & = & \sum\limits_{i=0}^{n-2}(n-i-1) = \sum\limits_{l=1}^{n-1}l = \frac{n(n-1)}{2} = \frac{n^2}{2} + \mathcal{O}(n) \end{array}$

Umspeicherungen:

Die i-Schleife wird (n-1)-mal durchlaufen.
Pro Durchlauf der i-Schleife werden 4 Umspeicherungen durchgeführt (zzgl. denen der j-Schleife).
Die j-Schleife wird (n-i-1)-mal aufgerufen.
Der if-Zweig innerhalb der j-Schleife wird dabei
im besten Fall nie
im schlechtesten Fall immer
im Mittel jedes zweite Mal
durchlaufen. Dabei erfolgt jeweils eine Umspeicherung, also insgesamt
im besten Fall 0
im schlechtesten Fall n-i-1
im Mittel (n-i-1)/2
Umspeicherungen.

Also:

$\begin{array}{lllll} U_{min}(n) & = & (n-1) \cdot 4 = 4 \cdot n + \mathcal{O}(1) & & \\ U_{max}(n) & = & (n-1) \cdot 4 + \sum\limits_{i=0}^{n-2}(n-i-1) & & \\ & = & (n-1)\cdot 4 + \frac{n \cdot (n-1)}{2} & = & \frac{n^2}{2} + \mathcal{O}(n)\\ U_{mid}(n) & = & (n-1) \cdot 4 + \sum\limits_{i=0}^{n-2}\frac{n-i-1}{2} & & \\ & = & (n-1) \cdot 4 + \frac{1}{2} \cdot \frac{n \cdot (n-1)}{2} & = & \frac{n^2}{4} + \mathcal{O}(n) \end{array}$

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.