\documentclass[a4paper,10pt]{scrartcl}
\setlength{\topmargin}{-2cm}
\setlength{\oddsidemargin}{-1cm}
\setlength{\evensidemargin}{-1cm}
\setlength{\textwidth}{18cm}
\setlength{\textheight}{24cm}

\usepackage[active]{srcltx}
\usepackage[german]{babel}
\usepackage[utf8]{inputenc}
\usepackage[pdftex,a4paper,colorlinks=true,linkcolor=black]{hyperref}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{graphicx}
%\usepackage{trfsigns}
\usepackage[usenames]{color}
\usepackage{listings}

% Shortcuts für Matrizen, '&' und '\\' gelten wie gewohnt
\newcommand{\mtrx}[1]{\begin{matrix}#1\end{matrix}} % ( normal Matrix )
\newcommand{\smtrx}[1]{\begin{smallmatrix}#1\end{smallmatrix}} % ( small Matrix )
\newcommand{\pmtrx}[1]{\begin{pmatrix}#1\end{pmatrix}}	% ( (...) )
\newcommand{\bmtrx}[1]{\begin{bmatrix}#1\end{bmatrix}}	% ( [...] )
\newcommand{\Bmtrx}[1]{\begin{Bmatrix}#1\end{Bmatrix}}	% ( {...} )
\newcommand{\e}{\text{e}}
\newcommand{\im}{\text{i}}

% code box
\setlength{\fboxrule}{1.2pt}
%\definecolor{codeFrame}{rgb}{0.1,0.1,0.1}
\definecolor{codeBg}{rgb}{0.96,0.96,0.96}
%\definecolor{codeFg}{rgb}{0.2,0.2,0.2}
%\definecolor{brown}{rgb}{0.6,0.3,0.3}
\definecolor{grey}{rgb}{0.4,0.4,0.4}
%\newcommand{\codebox}[1]{\fcolorbox{codeFrame}{codeBg}{\texttt{#1}}}
%\newcommand{\code}[2][codeFg]{\codebox{\textcolor{#1}{#2}}}

% paragraph settings, http://docutils.sourceforge.net/docs/user/latex.html
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}

\lstset{% general command to set parameter(s)
    basicstyle=\footnotesize,          % print whole listing small
    keywordstyle=\color{black}\ttfamily,
                                % underlined bold black keywords
    identifierstyle=,           % nothing happens
    commentstyle=\color{grey}, % white comments
    stringstyle=\color{brown}\ttfamily,      % typewriter type for strings
    showstringspaces=false,     % no special string spaces
    backgroundcolor=\color{codeBg},%
    framerule=0pt,%
    frame=single,%
    float=h,%
    extendedchars=true}
\lstset{language=Java}
\lstset{tabsize=2}

%opening
\title{Algorithmen und Datenstrukturen}
\author{Franz Brauße}

\begin{document}
%\maketitle
\tableofcontents

\section{Sortierverfahren}

\subsection{Bubblesort}
\begin{minipage}{\textwidth}
\subsection*{Eigenschaften}
\begin{itemize}
	\item in-place
	\item worst-case: $\Theta(n^2)$ (absteigend sortierter Input)
	\item best-case: $\Theta(n)$ (aufsteigend sortierter Input)
	\item sequentieller Zugriff auf Input
\end{itemize}

\subsection*{Code}
\begin{lstlisting}
	void bubbleSort(int[] A) {
		int n = A.length;
		do {
			boolean vertauscht = false;
			for (int i=1; i<n; i++)
				if (A[i] > A[i + 1]) {
					swap(A[i], A[i + 1]);
					vertauscht = true;
				}
			n--;
		} while (vertauscht && n >= 1);
	}
\end{lstlisting}
\end{minipage}

\subsection{Bucketsort}
\begin{minipage}{\textwidth}
\subsubsection*{Eigenschaften}
\begin{itemize}
	\item stabil
	\item Komplexität im best-/worst-case: $\mathcal O(n+k)$ mit $k =$ Anzahl Buckets; ist diese konstant, dann $\Theta(n)$
	\item out-of-place
\end{itemize}

\subsubsection*{Code}
\begin{lstlisting}
	void bucketSort(int[] a, int k) {
		// Histogramm erstellen
		int[] buckets = new int[k];
		for (int i=0; i<n; i++)
			buckets[a[i]]++;
		// sortieren
		int x = 0;
		for (int i=0; i<b; i++)
			while (buckets[i] > 0) {
				a[x++] = i;
				buckets[i]--;
			}
	}
\end{lstlisting}
\end{minipage}

\subsection{Selectionsort}
\begin{minipage}{\textwidth}
\subsubsection*{Eigenschaften}
\begin{itemize}
	\item in-place
	\item lässt sich stabil implementieren
	\item sequentieller Zugriff auf Input (selten große Seeks)
	\item Komplexität in $\mathcal O(n^2)$, da $n-1$-mal Bestimmung des Minimums und Vertauschung
		\[ \Rightarrow\sum_{i=1}^{n-1}i=\frac{(n-1)n}{2}=\frac{1}{2}n^2-n \in \mathcal O(n^2) \]
\end{itemize}

\subsubsection*{Code}
\begin{lstlisting}
	void selectionSort(int[] a) {
		for (int i=0; i<a.length; i++)
			swap(a, minPos(a, i), i);
	}
	
	int minPos(int[] a, int from) {
		for (int i=from; i<a.length; i++)
			if (a[i] < a[from])
				from = i;
		return from;
	}
\end{lstlisting}
\end{minipage}

\subsection{Quicksort}
\begin{minipage}{\textwidth}
\subsubsection*{Eigenschaften}
\begin{itemize}
	\item in-place
	\item kein sequentieller Zugriff, große Seeks (deshalb nicht für Listen geeignet)
	\item Komplexität:
		\begin{itemize}
			\item worst-case: Laufzeit in $\mathcal O(n^2)$, Rekursionsstackbedarf in $\mathcal O(n)$
				\begin{itemize}
					\item Input auf- oder absteigend vorsortiert
					\item Als Pivot wird stets das erste oder letzte Element verwandt
				\end{itemize}
			\item average-/best-case: Laufzeit in $\mathcal O(n \cdot \log n)$, Rekursionsstackbedarf in $\mathcal O(\log n)$
				\begin{itemize}
					\item Input unsortiert
					\item Wahl des Pivot so, dass die jeweils entstehenden Teillisten (ungefähr) gleich lang sind
				\end{itemize}
		\end{itemize}
\end{itemize}
\end{minipage}

\subsection{Mergesort}
\begin{minipage}{\textwidth}
\subsubsection*{Eigenschaften}
\begin{itemize}
	\item stabil
	\item worst-/average-/best-case: $\mathcal O(n \cdot \log n)$
	\item Speicherbedarf in $\mathcal O(n)$
	\item sequentieller Zugriff auf Input
\end{itemize}

\subsubsection*{Code}
\begin{lstlisting}
	int[] mergeSort(int[] a) {
		if (a.length <= 1)
			return a;
		int m = a.length / 2;
		int[] a1 = new int[m];
		int[] a2 = new int[a.length - m];
		return merge(
				mergesort(a1),
				mergesort(a2));
	}
	
	int[] merge(int[] a1, int[] a2) {
		int[] a = new int[a1.length + a2.length];
		int l = 0, r = 0, i = 0;
		while (l < a1.length && r < a2.length) {
			if (a1[l] <= a2[r]) {
				a[i++] = a1[l++];
			} else {
				a[i++] = a2[r++];
			}
		}
		while (l < a1.length)
			a[i++] = a1[l++];
		while (r < a2.length)
			a[i++] = a2[r++];
		return a;
	}
\end{lstlisting}
\end{minipage}

\subsection{Insertionsort}
\begin{minipage}{\textwidth}
\subsubsection*{Eigenschaften}
\begin{itemize}
	\item $\mathcal O(1)$ zusätzlicher Speicher, Laufzeitkomplexität:
		\begin{itemize}
			\item best-case: $\mathcal O(n)$ (Eingabe sortiert)
			\item worst-case: $\mathcal O(n^2)$ (Eingabe absteigend sortiert)
		\end{itemize}
	\item stabil
	\item braucht nicht alle Eingabedaten zu Beginn
\end{itemize}

\subsubsection*{Code}
\begin{lstlisting}
	void insertionSort(int[] a) {
		for (int i=2; i<n; i++) {
			int t = a[i], j;
			for (j=i; j>1; j--) {
				if (a[j - 1] >= t) break;
				a[j] = a[j - 1];
			}
			a[j] = t;
	}
\end{lstlisting}
\end{minipage}

\subsection{Heapsort}
\begin{minipage}{\textwidth}
\subsubsection*{Eigenschaften}
\begin{itemize}
	\item nicht stabil
	\item in-place
	\item Komplexität: $\mathcal O(n \cdot \log n)$
		\begin{itemize}
			\item worst-case: Input absteigend sortiert
			\item best-case: Input enthält viele gleiche Elemente
		\end{itemize}
	\item kein sequentieller Zugriff, große Seeks (deshalb nicht für Listen geeignet)
\end{itemize}
\begin{lstlisting}
	void heapSort(int[] a) {
		generateMaxHeap(a);												// Aufbauphase
		for (int i=a.length-1; i>0; i--) {				// Selektionsphase
			swap(a, i, 0);
			versenke(a, 0, i);
		}
	}
	
	void generateMaxHeap(int[] a) {
		for (int i=(a.length/2)-1; i>=0; i--)
			versenke(a, i, a.length);
	}
	
	void versenke(int[] a, int i,int n) {
		while (i <= (n / 2) - 1) {
			int kindIndex = ((i+1) * 2) - 1;				// Index des linken Kinds
			if (kindIndex + 1 < n)									// bestimme ob ein rechtes Kind existiert
				if (a[kindIndex] < a[kindIndex + 1])	// falls ja, gehe zu diesem
					kindIndex++;
			if (a[i] < a[kindIndex]) {
				swap(a, i, kindIndex);								// Element versenken
				i = kindIndex;												// wiederhole den Vorgang mit der neuen Position
			} else break;
		}
	}
\end{lstlisting}
\end{minipage}

\end{document}
