diff options
Diffstat (limited to 'sonstiges/sonstiges.tex')
| -rw-r--r-- | sonstiges/sonstiges.tex | 30 |
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} |