From f92e9b22b6e37921146afc542fcb0398ac407c47 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 23 Jan 2016 12:30:38 +0100 Subject: Removes section about sorting in linear time. --- sonstiges/radixSort.cpp | 24 ------------------------ 1 file changed, 24 deletions(-) delete mode 100644 sonstiges/radixSort.cpp (limited to 'sonstiges/radixSort.cpp') 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 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 &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 &a) { - int digits = getLongestNumber(a); - for (int d = 0; d < digits; d++) { - vector 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)); - } -} -- cgit v1.2.3