-
Notifications
You must be signed in to change notification settings - Fork 0
/
RadixSort.cpp
27 lines (25 loc) · 877 Bytes
/
RadixSort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int getDigit(int num, int factor) {
return (abs(num) / abs(factor)) % 10;
}
void radixCountingSort(vector<int> &nums, int factor) {
int freqSize = 10, size = nums.size();
vector<int> freq(freqSize, 0), sorted(size, 0);
for (int ind = 0; ind < size; ind++)
freq[getDigit(nums[ind], factor)]++;
for (int ind = 1; ind < freqSize; ind++)
freq[ind] += freq[ind - 1];
// for stable sorting start ind from end and decrement till 0
for (int ind = size - 1; ind >= 0; ind--)
sorted[freq[getDigit(nums[ind], factor)]-- - 1] = nums[ind];
nums = sorted;
}
void radixSort(vector<int> &nums) {
int minVal = *min_element(nums.begin(), nums.end());
for (auto &num : nums) num -= minVal;
int factor = 1, maxVal = *max_element(nums.begin(), nums.end());
while (maxVal / factor) {
radixCountingSort(nums, factor);
factor *= 10;
}
for (auto &num : nums) num += minVal;
}