TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 6

Geben Sie die Anzahl der Schlüsselvergleiche und Schlüsselbewegungen für Selection Sort und Insertion Sort in $\Theta$-Notation in Abhängigkeit von N an, wobei N eine beliebig große gerade Zahl sein kann, wenn die Eingabe folgendermaßen aussieht:

(a) $\frac{N}{2},\frac{N}{2}-1,\mathrm{...},0,\frac{N}{2}+1,\frac{N}{2}+2,\mathrm{...},N$

(b) $\frac{N}{2},\frac{N}{2}+1,\frac{N}{2}-1,\frac{N}{2}+2,\frac{N}{2}-2,\mathrm{...},2,N-1,1,N$

Lösung

(a)

Selection Sort:

 #Comparisons: ${\Sigma }_{k=1}^{N}k=(\genfrac{}{}{0ex}{}{N+1}{2})=\Theta (N^2)$
 #Movements: $\lceil \frac{N}{4}\rceil =\Theta (N)$

Insertion Sort:

 #Comparisons: ${\Sigma }_{k=1}^{\frac{N}{2}}k+\frac{N}{2}=(\genfrac{}{}{0ex}{}{\frac{N+2}{2}}{2})+\frac{N}{2}=\Theta (N^2)$
 #Movements: ${\Sigma }_{k=1}^{\frac{N}{2}}k=(\genfrac{}{}{0ex}{}{\frac{N+2}{2}}{2})=\Theta (N^2)$