diff options
| -rw-r--r-- | sonstiges/bucketSort.cpp | 16 | ||||
| -rw-r--r-- | sonstiges/radixSort.cpp | 23 | ||||
| -rw-r--r-- | sonstiges/sonstiges.tex | 30 | ||||
| -rw-r--r-- | tcr.pdf | bin | 177626 -> 179603 bytes | |||
| -rw-r--r-- | toDo.txt | 1 |
5 files changed, 45 insertions, 25 deletions
diff --git a/sonstiges/bucketSort.cpp b/sonstiges/bucketSort.cpp new file mode 100644 index 0000000..90533e1 --- /dev/null +++ b/sonstiges/bucketSort.cpp @@ -0,0 +1,16 @@ +vector<int> res; +void bucketSort(vector<int> &a) { //stores result in global vector res + int c[BUCKETS] = {0}; + for (int i = 0; i < (int)a.size(); i++) c[a[i]]++; + int C = 0; + for (int i = 0; i < BUCKETS; i++) { + int tmp = C; + C += c[i]; + c[i] = tmp; + } + res.resize(a.size()); + for (int i = 0; i < (int)a.size(); i++) { + res[c[a[i]]] = a[i]; + c[a[i]]++; + } +}
\ No newline at end of file diff --git a/sonstiges/radixSort.cpp b/sonstiges/radixSort.cpp new file mode 100644 index 0000000..5dbc02c --- /dev/null +++ b/sonstiges/radixSort.cpp @@ -0,0 +1,23 @@ +const int p[10] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; + +int getLongestNumber(vector<int> &a) { + int res = 0; + for (int i = 0; i < (int)a.size(); i++) res = max(res, (int)ceil(log10(a[i]) + 1)); + return res; +} + +int getIthDigit(int digit, int i) { + return (digit / p[i]) % 10; +} + +void radixSort(vector<int> &a) { + int digits = getLongestNumber(a); + for (int d = 0; d < digits; d++) { + vector<int> bucket[10]; + for(int i = 0; i < (int)a.size(); i++) + bucket[getIthDigit(a[i],d)].push_back(a[i]); + a.clear(); + for(int i = 0; i < 10; i++) + copy(bucket[i].begin(), bucket[i].end(), back_inserter(a)); + } +}
\ No newline at end of file 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} Binary files differ@@ -2,7 +2,6 @@ - bitonic tsp - josephus problem - min cost max flow -- linear time sorting - roman numerals - towers of hanoi - NIM GAMES (WICHTIG)
\ No newline at end of file |