\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 3},
  Thematik = {Quicksort},
  Referenz = 46114-2008-H.T2-A3,
  RelativerPfad = Examen/46114/2008/09/Thema-2/Aufgabe-3.tex,
  ZitatSchluessel = 46114:2008:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Teile-und-Herrsche (Divide-and-Conquer)},
  EinzelpruefungsNr = 46114,
  Jahr = 2008,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 3,
}

Quicksort ist ein Sortierungsverfahren, das nach dem
Divide-and-Conquer-Prinzip (Teile und Herrsche) arbeitet. Wir betrachten
im Folgenden die Anwendung dieses Verfahrens zum Sortieren von
Integerzahlen. Die Sortierung soll in aufsteigender Reihenfolge der
Werte erfolgen. Wir nehmen dabei an, dass die zu sortierenden Zahlen in
einem Feld fester Länge abgelegt sind.
\index{Teile-und-Herrsche (Divide-and-Conquer)}
\footcite{46114:2008:09}

\begin{enumerate}

%%
% (a)
%%

\item Beschreiben Sie die Arbeitsweise des Divide-and-Conquer-Prinzips
im allgemeinen Fall. Geben Sie dabei die Bedeutung der Schritte divide,
conquer und combine an.

%%
% (b)
%%

\item Beschreiben Sie die Arbeitsweise des Algoritumus Quicksort. Geben
Sie dabei an, worin die Schritte divide, conquer und combine im
konkreten Fall bestehen.

%%
% (e)
%%

\item Geben Sie in C, C++ oder Java eine Implementierung des Algorithmus
Quicksort an. Formulieren Sie die Implementierung als rekursive Funktion
quicksort() und verwenden Sie das jeweils erste Element. des
(Teil-)Feldes für die Aufteilung Verwenden Sie für Ihre Implementierung
von quicksort() «lei Parameter:
\begin{enumerate}
\item

das Feld, in dem die zu sortierenden Zahlen abgelogt sind:

\item

den Index des am weitesten links gelegenen Elementes des zu sortierenden
Teilfeldes;

\item

den Index des am weitesten rechts gelegenen Elementes des zu
sortierenden Teilfeldes.
\end{enumerate}

Erläutern Sie die Arbeitsweise Ihrer Implementierung. Kennzeichnen Sie
die Schritte divide, conquer und combine des zugrundeliegenden
Divide-and-Conquer-Prinzips.
\end{enumerate}
\end{document}