Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.
Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
-folgenden Algorithmen benötigen ein (einfaches) Sortiernetzwerk als
+folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
Algorithmen.
Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
veröffentlicht wurde. Es ist deutlich effizienter als das
-Odd-Even-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
+Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der
Schichten.
verleiht dem Sortiernetzwerk seinen Namen.
Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
-Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist,
-$\operatorname{BS}(n = 2^t)$.
+Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
+Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
-Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie
-das \emph{bitonen Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
+Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
+das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
projects / diplomarbeit.git / commitdiff