Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
\section{Eigenschaften von Sortieralgorithmen}
\subsection{Laufzeit}
Wir haben bereits umfangreiche Laufzeitanalysen von Sortieralgorithmen durchgeführt. Die Qualität eines
Sortieralgorithmus anhand seines best/worst/average-case-Verhaltens zu beurteilen, scheint also naheliegend.
\subsection{worst-case-optimal}
Im Zusammenhang von vergleichsbasierten Sortieralgorithmen bedeutet die Eigenschaft worst-case-optimal, dass die
Untergrenze von $Ω(n \log n)$ \emph{immer} eingehalten wird.
\subsection{Stabilität}
Ein Sortieralgorithmus ist stabil, wenn durch das Sortieren die Reihenfolge innerhalb bezüglich der Quasiordnung
gleicher Elemente gewährleistet ist.
Formaler:
\begin{definition}[Stabilität]
Sei $[x_0, x_1, \cdots, x_{n-1}]$ ein Array bzw eine Sequenz von $n$ Elementen aus der Menge $X$. Unterhalte
$X$ eine totale Quasiordnung, unter derer ``Gleichheit'' von $x, x' \in X$ mit $x \equiv x'$ bezeichnet wird. Sei das
Wirken des Sortieralgorithmus $f$ eine Permutation $π \in \text{Perm}(n)$, also $f([x_0, \cdots x_{n-1}]) =
[x_{π(0)}, x_{π(1)}, \cdots, x_{π(n-1)}]$.
Dann ist unser Sortieralgorithmus stabil, wenn gilt:
\[
x_i \equiv x_{i'} \text{ und } i \leq i' \text{ impliziert } π(i) \leq π(i').
\]
\end{definition}
\subsection{in-place}
Als \emph{in-place} bezeichnet man die Eigenschaft eines Sortieralgorithmus, neben dem Speicherverbrauch des Inputarrays
nur einen konstanten zusätzlichen Speicherverbrauch zu haben. Es ist also $S_{\text{alg}} \in \mathcal{O}(1)$.
Gelegentlich wird auch Speicherverbrauch von $\mathcal{O}(\log n)$ noch als \emph{in-place} bezeichnet.
\subsection{Adaptivität}
Als adaptiv bezeichnet man einen Sortieralgorithmus, der kürzere Laufzeiten hat, wenn Teile des Arrays bereits sortiert
sind. Insbesondere muss der best-case also in $\mathcal{O}(n)$ liegen.
\subsection{Parallelisierbarkeit}
Sowohl auf dem PC, als auch im Smartphone und inbesondere in einem Rechenzentrum wird zusätzliche Rechenleistung fast
nurnoch durch parallele Architekturen erreicht. Damit gewinnt auch die Frage nach paralleisierbarkt größere Bedeutung.
Aus einer theoretischen Perspektive nimmt man dabei oftmals unbegrenzt viele parallele Prozessoren an.