Sortierverfahren | MathePrisma

Für die Aufwandsanalyse orientieren wir uns am C-Programm.
Wir zählen Schlüsselvergleiche V und (Datensatz-) Umspeicherungen U.

Schlüsselvergleiche:

Im besten Fall sind die Datensätze bereits sortiert.

Dann wird die i-Schleife (wie in allen anderen Fällen auch) genau (n-1)-mal durchlaufen.
In jedem Durchlauf wird ein Schlüsselvergleich durchgeführt,
der if-Zweig wird aber nie durchlaufen.

Also:

$\displaystyle V_{min}(n) = (n-1) \cdot 1 = n + \mathcal{O}(1)$

Im schlechtesten Fall wird der if-Zweig in jedem Durchlauf der i-Schleife durchlaufen.

Dann wird die i-Schleife (wie in allen anderen Fällen auch) genau (n-1)-mal durchlaufen.
In jedem Durchlauf wird ein Schlüsselvergleich durchgeführt,
der if-Zweig wird jedesmal durchlaufen.
Im if-Zweig wird eine do-while-Schleife durchgeführt.
Diese wird (im schlechtesten Fall) i-mal durchlaufen.
Jeder Durchlauf erfordert dabei einen Schlüsselvergleich.

Also:

$\displaystyle V_{max}(n)= (n-1) + \sum\limits_{i=1}^{n-1} i = \frac{n^2}{2} + \frac{n}{2} - 1 = \frac{n^2}{2} + \mathcal{O}(n)$

Im Mittel wird

die i-Schleife wieder genau (n-1)-mal durchlaufen.
In jedem Durchlauf wird ein Schlüsselvergleich durchgeführt.
Der if-Zweig wird in jedem Durchlauf der i-Schleife 0.5-mal durchlaufen
(d.h. bei der Häfte der Durchläufe wird der if-Zweig durchlaufen).
Die do-while-Schleife innerhalb des if-Zweigs wird also (i+1)/2-mal durchlaufen.
Jeder Durchlauf erfordert dabei einen Schlüsselvergleich.

Also:

$\displaystyle V_{mid}(n) = (n-1) + 0.5 \cdot \sum\limits_{i=1}^{n-1} \frac{i+1}{2} = \frac{n^2}{8} + \mathcal{O}(n)$

Umspeicherungen:

Im besten Fall sind die Datensätze bereits sortiert, d.h.

in der i-Schleife sind keine Umspeicherungen notwendig.

Also:

$\displaystyle U_{min}(n) = 0$

Im schlechtesten Fall wird

in jedem der n-1 Durchläufe der i-Schleife der if-Zweig einmal durchlaufen.
Im if-Zweig werden zwei Umspeicherungen und eine do-while-Schleife durchgeführt.
Die do-while-Schleife wird (im schlechtesten Fall) i-mal durchlaufen.
Jeder Durchlauf erfordert dabei eine Umspeicherung.

Also:

$\displaystyle U_{max}(n) = (n-1) \cdot 2 + \sum\limits_{i=1}^{n-1} i = \frac{n^2}{2} + \frac{3}{2}n - 2 = \frac{n^2}{2} + \mathcal{O}(n)$

Im Mittel wird

in jedem der n-1 Durchläufe der i-Schleife der if-Zweig 0.5-mal durchlaufen
(d.h. bei der Häfte der Durchläufe wird der if-Zweig durchlaufen).
Im if-Zweig werden zwei Umspeicherungen und eine do-while-Schleife durchgeführt.
Die do-while-Schleife wird im Mittel (i+1)/2-mal durchlaufen.
Jeder Durchlauf erfordert dabei eine Umspeicherung.

Also:

$\displaystyle U_{mid}(n) = 0.5 \cdot \Biggl( (n-1) \cdot 2 + \sum\limits_{i=1}^{n-1} \frac{i+1}{2} \Biggr) = \frac{n^2}{8} + \mathcal{O}(n)$

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.