\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)$ auch die asymptotische Obergrenze ist, also die worst-case-Laufzeit in i$Θ(n \log n)$ 
liegt.

\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. Diese Definition lässt sich mittels
Fehlstellungen präzisieren:

\begin{definition}[Fehlstände und Fehlstandszahl]
  Sei $A$ eine geordnete Menge und sei $[a_1, \dots, a_n] \in A^n$ eine Folge von Elementen in $A$. Die Anzahl der
  Fehlstände bezüglich $a_i$ ist 
  \[
    f_i := |\{a_j : j > i, a_j < a_i \}|,
  \]
  also alle Elemente die rechts von $a_i$ liegen, obwohl sie bei einer geordneten Folge links von $a_i$ liegen sollten.
  Die Summe aller Fehlstände einer solchen Folge ist die Fehlstandszahl
  \[
    F([a_1, \dots, a_n]) := \sum_{i=1}^n f_i.
  \]
\end{definition}

Die Fehlstandszahl ist $F([1,2,3, \dots ,n]) = 0$, falls wir eine vollständig sortierte Folge haben, ist bei einer
einzelnen Vertauschung von zwei Nachbarn $1$ und wir bei einem invers sortierten Array maximiert:
$F([n,n-1,\dots,1]) = \sum_{i=1}^{n-1} i = \frac{n^2 - n}{2}$.

Adaptiv im strengeren Sinne bedeutet nun, dass sich die (asymptotische) Laufzeit auch in Abhängigkeit zu den Fehlständen
ausdrücken lässt und geringer wird, wenn weniger Fehlstände vorliegen.

Allerdings wird die Definition von adaptiv landläufig auch etwas lockerer gehandhabt und umfasst auch das Erkennen invers sortierter
Teilsequenzen. Diese stellen in unserer Definition aber gerade den maximal schlimmsten Fall dar.

TODO: Beispiel \texttt{insertionsort}.


\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. 


TODO: Tabelle