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,...,0,{\frac {N}{2}}+1,{\frac {N}{2}}+2,...,N$

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

Lösung

(a)

Selection Sort:

 #Comparisons: $\Sigma _{k=1}^{N}{k}={\binom {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}}={\binom {\frac {N+2}{2}}{2}}+{\frac {N}{2}}=\Theta (N^{2})$
 #Movements: $\Sigma _{k=1}^{\frac {N}{2}}k={\binom {\frac {N+2}{2}}{2}}=\Theta (N^{2})$