\section{Radixsort}
TODO: Das Kapitel braucht mehr Bilder

Der Sortieralgorithmus \texttt{radixsort} ist ein Beispiel für ein nicht vergleichsbasiertes Sortierverfahren. Nicht vergleichsbasierte Sortierverfahren
arbeiten ohne Vergleiche und müssen daher zusätzliche Annahmen über den Input machen. Wir fordern also, dass unser aus
$n$ Elementen bestehender Input jeweils eine gleiche Anzahl von Stellen $d \in \mathbb{N}$ hat. Pro Stelle haben wir
dabei $b$ verschiedene Möglichkeiten. Beispielsweise besteht \texttt{``beispiel''} aus $d=8$ Buchstaben, von denen es
$b=26$ gibt. Die Dezimalzahl $9215$ hat hingegen $d=4$ Stellen mit jeweils $b=10$ Möglichkeiten. Wir referenzerieren
auf die $i.$ Stelle von $x$ mit $x_i$. Beispielsweise ist mit $x=423$: $x_0=4$, $x_2=3$.

Hat man Zahlen/Wörter von unterschiedlicher Länge, muss man sie von der passenden Seite mit Lückenfüllern auffüllen, im
Fall von Zahlen also von links mit $0$.

Die Idee von \texttt{radixsort} ist nun, von der unsignifikantesten Stelle (bei uns an letzter Stelle) ausgehend bis zur
signifikantesten (ersten) Stelle immer jeweils einmal zu \emph{streuen} und dann zu \emph{sammeln}. In der Streuphase
werden die Elemente in die jeweiligen Kategorien einsortiert (unter strikter Einhaltung einer vorher vorhandenen
Reihenfolge). In der Sammelphase werden alle Kategorien entsprechend ihrer Ordnung untereinander wieder konkateniert.

\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{$\texttt{radixsort}(\mathcal{Q})$}
  \KwIn{An unsorted Queue $\mathcal{Q}$ of length $n$} 
  \KwOut{$\mathcal{Q}$, but sorted}
  $\text{Initialize Queues } \mathcal{Q}_0, \dots, \mathcal{Q}_{b-1}$ \;
  \For{$i \leftarrow d-1$ \KwTo $0$}{
    \While{$\mathcal{Q}$ \emph{is not empty}}{
      $x \leftarrow \texttt{get}(\mathcal{Q})$ \;
      $\texttt{put}(\mathcal{Q}_{x_i}, x)$ \;
    }
    \For{ $j \rightarrow 0$ \KwTo $b-1$}{
      \While{$\mathcal{Q}_j$ \emph{is not empty}}{
        $\texttt{put}(\mathcal{Q}, \texttt{get}(\mathcal{Q}_j))$ \;
      }
    }
  }
  \KwRet $\mathcal{Q}$
\end{algorithm}

Die Zeilen 3-5 werden \emph{Streuphase} genannt, und Zeile 6-8 bezeichnet man auch als \emph{Sammelphase}.
Der Algorithmus \texttt{radixsort} ist korrekt, da nach den ersten $i$ Durchläufen von Zeile 2 die Elemente, eingeschränkt auf die
letzten $i$ Stellen, sortiert sind.
Eine wichtige Bedingung für die Korrektheit der Sammelphase ist, dass die vorige Reihenfolge innerhalb der Fächer
aufrechterhalten wird.

Die Laufzeit von \texttt{radixsort} beträgt $T_{\text{rs}}(n) = \mathcal{O}(d \cdot n)$, ist also linear, wenn die
Anzahl der Stellen $d$ als konstant betrachtet wird.
In diesem Fall ist \texttt{radixsort} asymptotisch schneller als vergleichsbasierte Sortierverfahren, hat aber einen
deutlich erhöhten Speicherbedarf, welcher insbesondere linear in der Anzahl der Fächer $b$ wächst.
