linear time sorting

1 files changed, 6 insertions, 24 deletions

diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex
index 2fb91f1..1a51ad9 100644
--- a/sonstiges/sonstiges.tex
+++ b/sonstiges/sonstiges.tex
@@ -8,29 +8,11 @@
 	\item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt.
 \end{enumerate}
 
-\subsection{Linear time sorting}
+\subsection{Sortieren in Linearzeit}
+Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Bucketsort \lstinline{bucketSort(vector<int> ..., n);} schneller.
 
-\begin{lstlisting}
-int p[10] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
+\subsubsection{Bucketsort}
+\lstinputlisting{sonstiges/bucketSort.cpp}
 
-int get_i_th_digit(int digit, int i) {
-	return (digit / p[i]) % 10;
-}
-
-void sortLinear(vector<int> &s) {
-	int max_digit;
-	for(int i = 0; i < s.size(); i++) {
-		int digit = ceil(log10(s[i]));
-		if(digit > max_digit)
-			max_digit = digit;
-	}
-	for(int d = 0; d < max_digit; d++) {
-		vector<vector<int>> bucket(10);
-		for(int i = 0; i < s.size(); i++)
-			bucket[get_i_th_digit(s[i],d)].push_back(s[i]);
-		s.clear();
-		for(int i = 0; i < 10; i++)
-			copy(bucket[i].begin(), bucket[i].end(), back_inserter(s));
-	}
-}
-\end{lstlisting}
+\subsubsection{LSD-Radixsort}
+\lstinputlisting{sonstiges/radixsort.cpp}