diff options
Diffstat (limited to 'sonstiges')
| -rw-r--r-- | sonstiges/bucketSort.cpp | 16 | ||||
| -rw-r--r-- | sonstiges/radixSort.cpp | 24 | ||||
| -rw-r--r-- | sonstiges/sonstiges.tex | 9 |
3 files changed, 0 insertions, 49 deletions
diff --git a/sonstiges/bucketSort.cpp b/sonstiges/bucketSort.cpp deleted file mode 100644 index 90533e1..0000000 --- a/sonstiges/bucketSort.cpp +++ /dev/null @@ -1,16 +0,0 @@ -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 deleted file mode 100644 index 7ca51f6..0000000 --- a/sonstiges/radixSort.cpp +++ /dev/null @@ -1,24 +0,0 @@ -//Comparable with sort from <algorithms> in a range from 0 to 5000, for values greater than 5000 use sort -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)); - } -} diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex index 1f111bc..b2d9009 100644 --- a/sonstiges/sonstiges.tex +++ b/sonstiges/sonstiges.tex @@ -8,15 +8,6 @@ \item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt. \end{enumerate} -\subsection{Sortieren in Linearzeit} -Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Bucketsort schneller. - -\subsubsection{Bucketsort} -\lstinputlisting{sonstiges/bucketSort.cpp} - -\subsubsection{LSD-Radixsort} -\lstinputlisting{sonstiges/radixSort.cpp} - \subsection{Bit Operations} \lstinputlisting{sonstiges/bitOps.cpp} |