1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
//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));
}
}
|
