Adding Linear time sorting

1 files changed, 28 insertions, 1 deletions

diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex
index 09ea14c..2fb91f1 100644
--- a/sonstiges/sonstiges.tex
+++ b/sonstiges/sonstiges.tex
@@ -6,4 +6,31 @@
 	\item Implikationsgraph bauen, $\left(a \vee b\right)$ wird zu $\neg a \Rightarrow b$ und $\neg b \Rightarrow a$.
 	\item Finde die starken Zusammenhangskomponenten.
 	\item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt.
-\end{enumerate}
\ No newline at end of file
+\end{enumerate}
+
+\subsection{Linear time sorting}
+
+\begin{lstlisting}
+int p[10] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
+
+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}