\documentclass{bschlangaul-aufgabe}
\bLadePakete{java}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {Top-Level-Domains (TLD)},
  Referenz = 66115-2017-F.T1-A2,
  RelativerPfad = Examen/66115/2017/03/Thema-1/Aufgabe-2.tex,
  ZitatSchluessel = examen:66115:2017:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Sortieralgorithmen, Bucketsort, Radixsort, Mergesort, Quicksort},
  EinzelpruefungsNr = 66115,
  Jahr = 2017,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 2,
}

% fett
\let\f=\textbf
% unterstrich
\def\u{\_}
\def\U{\textbf{\_}}

In\index{Sortieralgorithmen} \footcite{examen:66115:2017:03} dieser
Aufgabe sei vereinfachend angenommen, dass sich Top-Level-Domains (TLD)
ausschließlich aus zwei oder drei der 26 Kleinbuchstaben des deutschen
Alphabets ohne Umlaute zusammensetzen. Im Folgenden sollen TLDs
lexikographisch aufsteigend sortiert werden, \dh eine TLD $(s_1, s_2)$
mit zwei Buchstaben (z. B. „co“ für Kolumbien) wird also vor einer TLD
$(t_1, t_2, t_3)$ der Länge drei (z. B. „com“) einsortiert, wenn $s_1 <
t_1 \lor (s_1 = t_1 \land s_2 \leq t_2)$ gilt.

\begin{enumerate}

%%
% a)
%%

\item Sortieren Sie zunächst die Reihung [„de“, „com“, „uk“, „org“,
„co“, „net“, „fr“, „ee“] schrittweise unter Verwendung des
Radix-Sortierverfahrens (Bucketsort). Erstellen Sie dazu eine Tabelle
wie das folgende Muster und tragen Sie dabei in das Feld „Stelle“ die
Position des Buchstabens ein, nach dem im jeweiligen Durchgang sortiert
wird (das Zeichen am TLD-Anfang habe dabei die „Stelle“ 1).
\index{Bucketsort}\index{Radixsort}

\begin{bExkurs}[Alphabet]
abcdefghijklmnopqrstuvwxyz
\end{bExkurs}

\begin{bAntwort}
\begin{tabular}{lllllllll}
Stelle & \multicolumn{7}{l}{Reihung} \\
       & de\u     & com      & uk\u     & org      & co\u     & net     & fr\u     & ee\u     \\
3      & de\U     & uk\U     & co\U     & fr\U     & ee\U     & or\f{g} & co\f{m}  & ne\f{t}  \\
2      & d\f{e}\u & e\f{e}\u & n\f{e}t  & u\f{k}\u & c\f{o}\u & c\f{o}m & f\f{r}\u & o\f{r}g  \\
1      & \f{c}o\u & \f{c}om  & \f{d}e\u & \f{e}e\u & \f{f}r\u & \f{n}et & \f{o}rg  & \f{u}k\u \\
\end{tabular}
\end{bAntwort}

%%
% b)
%%

\item Sortieren Sie nun die gleiche Reihung wieder schrittweise, diesmal
jedoch unter Verwendung des Mergesort-Verfahrens (Sortieren durch
Mischen). Erstellen Sie dazu eine Tabelle wie das folgende Muster und
vermerken Sie in der ersten Spalte jeweils welche Operation durchgeführt
wurde: Wenn Sie die Reihung geteilt haben, schreiben Sie in die linke
Spalte ein T und markieren Sie die Stelle, an der Sie die Reihung
geteilt haben, mit einem senkrechten Strich „|“. Wenn Sie zwei
Teilreihungen durch Mischen zusammengeführt haben, schreiben Sie ein M
in die linke Spalte und unterstreichen Sie die zusammengemischten
Einträge. Beginnen Sie mit dem rekursiven Abstieg immer in der linken
Hälfte einer (Teil-)Reihung.
\index{Mergesort}

% 1 co
% 2 com
% 3 de
% 4 ee
% 5 fr
% 6 net
% 7 org
% 8 uk

\begin{verbatim}
O | Reihung
T | de_   com   uk_   org | co_   net   fr_   ee_
T | de_   com | uk_   org
T | de_ | com
M | com   de_
T |             uk_ | org
M |             org   uk_
M | com   de_   org   uk_
T |                         co_   net | fr_   ee_
T |                         co_ | net
M |                         co_   net
T |                                     fr_ | ee_
T |                                     ee_ | fr_
M |                         co_   ee_   fr_   net
M | co_   com   de_   ee_   fr_   net   org   uk_
\end{verbatim}

%%
% c)
%%

\item Implementieren Sie das Sortierverfahren Quicksort für String-TLDs
in einer gängigen Programmiersprache Ihrer Wahl. Ihr Programm (Ihre
Methode) wird mit drei Parametern gestartet: dem String-Array mit den zu
sortierenden TLDs selbst sowie jeweils der Position des ersten und des
letzten zu sortierenden Eintrags im Array.
\index{Quicksort}

\begin{bAntwort}
\bJavaExamen{66115}{2017}{03}{Quicksort}
\end{bAntwort}

\end{enumerate}
\end{document}