\documentclass{bschlangaul-aufgabe}
\bLadePakete{java}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 8},
  Thematik = {Sortieren von 15,4,10,7,1,8,10 mit Bubble- und Selectionsort},
  Referenz = 66115-2018-H.T2-A8,
  RelativerPfad = Examen/66115/2018/09/Thema-2/Aufgabe-8.tex,
  ZitatSchluessel = examen:66115:2018:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Sortieralgorithmen, Bubblesort, Selectionsort, Algorithmische Komplexität (O-Notation)},
  EinzelpruefungsNr = 66115,
  Jahr = 2018,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 8,
}

Gegeben sei das folgende Feld $A$ mit $7$ Schlüsseln:
\index{Sortieralgorithmen}
\footcite{examen:66115:2018:09}

\begin{center}
[15, 4, 10, 7, 1, 8, 10]
\end{center}

\begin{enumerate}

%%
% (a)
%%

\item Sortieren Sie das Feld mittels des Sortierverfahrens
\emph{Bubblesort}. Markieren Sie jeweils, welche zwei Feldwerte
verglichen werden und geben Sie den Zustand des gesamten Feldes jeweils
neu an, wenn Sie eine Vertauschung durchgeführt haben.
\index{Bubblesort}

\begin{bAntwort}
% bschlangaul-werkzeug.java sortiere 15 4 10 7 1 8 10 -b
\begin{verbatim}
 15  4   10  7   1   8   10  Eingabe
 15  4   10  7   1   8   10  Durchlauf Nr. 1
>15  4<  10  7   1   8   10  vertausche (i 0<>1)
 4  >15  10< 7   1   8   10  vertausche (i 1<>2)
 4   10 >15  7<  1   8   10  vertausche (i 2<>3)
 4   10  7  >15  1<  8   10  vertausche (i 3<>4)
 4   10  7   1  >15  8<  10  vertausche (i 4<>5)
 4   10  7   1   8  >15  10< vertausche (i 5<>6)
 4   10  7   1   8   10  15  Durchlauf Nr. 2
 4  >10  7<  1   8   10  15  vertausche (i 1<>2)
 4   7  >10  1<  8   10  15  vertausche (i 2<>3)
 4   7   1  >10  8<  10  15  vertausche (i 3<>4)
 4   7   1   8   10  10  15  Durchlauf Nr. 3
 4  >7   1<  8   10  10  15  vertausche (i 1<>2)
 4   1   7   8   10  10  15  Durchlauf Nr. 4
>4   1<  7   8   10  10  15  vertausche (i 0<>1)
 1   4   7   8   10  10  15  Durchlauf Nr. 5
 1   4   7   8   10  10  15  Ausgabe
\end{verbatim}
\end{bAntwort}

%%
% (b)
%%

\item Sortieren Sie das Feld mittels des Sortierverfahrens
\emph{Selectionsort}. Markieren Sie jeweils, welche zwei Feldwerte
verglichen werden und geben Sie den Zustand des gesamten Feldes jeweils
neu an, wenn Sie eine Vertauschung durchgeführt haben.
\index{Selectionsort}

\begin{bAntwort}
% bschlangaul-werkzeug.java sortiere 15 4 10 7 1 8 10 -s
\begin{verbatim}
 15  4   10  7   1   8   10  Eingabe
 15  4   10  7   1   8   10* markiere (i 6)
>15  4   10  7   1   8   10< vertausche (i 0<>6)
 10  4   10  7   1   8*  15  markiere (i 5)
>10  4   10  7   1   8<  15  vertausche (i 0<>5)
 8   4   10  7   1*  10  15  markiere (i 4)
 8   4  >10  7   1<  10  15  vertausche (i 2<>4)
 8   4   1   7*  10  10  15  markiere (i 3)
>8   4   1   7<  10  10  15  vertausche (i 0<>3)
 7   4   1*  8   10  10  15  markiere (i 2)
>7   4   1<  8   10  10  15  vertausche (i 0<>2)
 1   4*  7   8   10  10  15  markiere (i 1)
 1  >4   7   8   10  10  15  vertausche (i 1<>1)
 1*  4   7   8   10  10  15  markiere (i 0)
>1   4   7   8   10  10  15  vertausche (i 0<>0)
 1   4   7   8   10  10  15  Ausgabe
\end{verbatim}
\end{bAntwort}

%%
% (c)
%%

\item Vergleichen Sie beide Sortierverfahren hinsichtlich ihres
Laufzeitverhaltens im \emph{best case}. Welches Verfahren ist in dieser
Hinsicht besser, wenn das zu sortierende Feld anfangs bereits sortiert
ist? Begründen Sie Ihre Antwort.
\index{Algorithmische Komplexität (O-Notation)}

\begin{bAntwort}
Der Bubblesort-Algorithmus hat im \emph{best case} eine Laufzeit von
$\mathcal{O}(n)$, der Selectionsort-Algorithmus $\mathcal{O}(n^2)$.

Bubblesort steuert seine äußere bedingte Wiederholung in vielen
Implementationen über eine boolsche Hilfvariable \bJavaCode{getauscht},
die beim Betreten der Schleife erstmals auf falsch gesetzt wird. Erst
wenn Vertauschungen vergenommen werden müssen, wird diese Varialbe auf
wahr gesetzt und die äußere Schleife läuft ein weiteres Mal ab. Ist das
zu sortierende Feld bereits sortiert, durchsucht der Algorithmus des
Bubblesort das Feld einmal und terminiert dann.

Der Selectionsort-Algorithmus hingegen ist mit zwei ineinander
verschränkten Schleifen umgesetzt, deren Wiederholungsanzahl sich starr
nach der Anzahl der Elemente im Feld richtet.

\bPseudoUeberschrift{Bubblesort}

\bJavaDatei[firstline=15,lastline=27]{sortier/BubbleIterativ}

\bPseudoUeberschrift{Selectionsort}

\bJavaDatei[firstline=12,lastline=30]{sortier/SelectionRechtsIterativ}
\end{bAntwort}

\end{enumerate}
\end{document}