Ok, so first of all i don't know if it exist. But i will share my algorithm here only.↵
↵
MOTIVATION!↵
==========↵
**Radix sort with base > 10?**↵
↵
so my motivation came when i though of why can't we use base 1e5 or 1e6 in radix sort? and i came up with following idea.↵
↵
Most of the questions on CF have limit of values <=1e9. So my algorithm focuses majorily on that thing.↵
↵
↵
Alogirthm.↵
=========↵
let us define a constant **base**, now we will make groups on the basis of ai % base,↵
↵
- group[j] -> contains ai / base of those whoose ai % base == j.↵
- counts[j] -> it will store total number of times ai / base is equal to j.↵
Note that both arrays will be of length base.↵
↵
#### Next question — Now, how can we find the index(in sorted array) of any value of any group?↵
Observe, let **x** be any value of group[i], then value = x * base + i, its index will be atleast bigger than prefix Sum of counts[i] upto x — 1,↵
also value will be bigger than those value whoose group number is smaller with same **x**.↵
↵
### Final touch↵
1. After making groups, and counts make prefix array of counts(let us call that array **pref**).↵
2. Define another array **Live** of length base, (initate all elements with 0).↵
3. Iterate from group 0 -> base.↵
Now for every element(x) in this group(i) do the following↵
- value = x * base + i↵
- the index of this value = pref[x — 1] + live[x]↵
- now do live[x] += 1↵
- Update array[index] = value.↵
4. the sorting is done!↵
↵
Implementation!↵
===============↵
↵
~~~~~↵
void sortit(vector<int> &arr, int base = 1 << 15) {↵
int n = arr.size();↵
↵
vector<vector<int>> grps(base);↵
vector<int> cnts(base + 1), live(base);↵
for (int i = 0; i < n; i++) {↵
int z = arr[i] / base;↵
grps[arr[i] % base].push_back(z);//adding each element in respective group↵
cnts[z + 1]++;//increasing count↵
}↵
for (int i = 1; i < base; i++) cnts[i] += cnts[i - 1]; //making prefix array↵
↵
for (int i = 0; i < base; i++) {↵
for (int &x : grps[i]) arr[cnts[x] + live[x]++] = x * base + i;↵
}↵
}↵
~~~~~↵
↵
Analysis.↵
=========↵
For all values less than base^2(base = 2^15), the time complexity comes out to be **O(n + base)**, 2 * n(2 for loops of n) + base(memory definition and prefix array). you can choose base depending on max value of array, N and memory.↵
↵
For n > base it starts becoming faster and faster than cpp sort.↵
↵
Results.↵
========↵
↵
These results are when i ran them on my laptop.↵
### Size 1000 Sorting....↵
Time taken by sortit() -> 1ms↵
Time taken by cpp sort() -> 0ms↵
↵
### Size 10000 Sorting....↵
Time taken by sortit() -> 2ms↵
Time taken by cpp sort() -> 1ms↵
↵
### Size 100000 Sorting....↵
Time taken by sortit() -> 9ms↵
Time taken by cpp sort() -> 15ms↵
↵
### Size 1000000 Sorting....↵
Time taken by sortit() -> 43ms↵
Time taken by cpp sort() -> 186ms↵
↵
### Size 10000000 Sorting....↵
Time taken by sortit() -> 331ms↵
Time taken by cpp sort() -> 2117ms↵
↵
### Size 100000000 Sorting....↵
Time taken by sortit() -> 3024ms↵
Time taken by cpp sort() -> 24147ms↵
↵
### Size 1000000000 Sorting....↵
Time taken by sortit() -> 50924ms↵
Time taken by cpp sort() -> 277987ms↵
↵
For higher values of n, it tends to become faster.↵
↵
If you find any similar or same algorithm, please let me know!↵
↵
↵
↵
↵
↵
↵
MOTIVATION!↵
==========↵
**Radix sort with base > 10?**↵
↵
so my motivation came when i though of why can't we use base 1e5 or 1e6 in radix sort? and i came up with following idea.↵
↵
Most of the questions on CF have limit of values <=1e9. So my algorithm focuses majorily on that thing.↵
↵
↵
Alogirthm.↵
=========↵
let us define a constant **base**, now we will make groups on the basis of ai % base,↵
↵
- group[j] -> contains ai / base of those whoose ai % base == j.↵
- counts[j] -> it will store total number of times ai / base is equal to j.↵
Note that both arrays will be of length base.↵
↵
#### Next question — Now, how can we find the index(in sorted array) of any value of any group?↵
Observe, let **x** be any value of group[i], then value = x * base + i, its index will be atleast bigger than prefix Sum of counts[i] upto x — 1,↵
also value will be bigger than those value whoose group number is smaller with same **x**.↵
↵
### Final touch↵
1. After making groups, and counts make prefix array of counts(let us call that array **pref**).↵
2. Define another array **Live** of length base, (initate all elements with 0).↵
3. Iterate from group 0 -> base.↵
Now for every element(x) in this group(i) do the following↵
- value = x * base + i↵
- the index of this value = pref[x — 1] + live[x]↵
- now do live[x] += 1↵
- Update array[index] = value.↵
4. the sorting is done!↵
↵
Implementation!↵
===============↵
↵
~~~~~↵
void sortit(vector<int> &arr, int base = 1 << 15) {↵
int n = arr.size();↵
↵
vector<vector<int>> grps(base);↵
vector<int> cnts(base + 1), live(base);↵
for (int i = 0; i < n; i++) {↵
int z = arr[i] / base;↵
grps[arr[i] % base].push_back(z);//adding each element in respective group↵
cnts[z + 1]++;//increasing count↵
}↵
for (int i = 1; i < base; i++) cnts[i] += cnts[i - 1]; //making prefix array↵
↵
for (int i = 0; i < base; i++) {↵
for (int &x : grps[i]) arr[cnts[x] + live[x]++] = x * base + i;↵
}↵
}↵
~~~~~↵
↵
Analysis.↵
=========↵
For all values less than base^2(base = 2^15), the time complexity comes out to be **O(n + base)**, 2 * n(2 for loops of n) + base(memory definition and prefix array). you can choose base depending on max value of array, N and memory.↵
↵
For n > base it starts becoming faster and faster than cpp sort.↵
↵
Results.↵
========↵
↵
These results are when i ran them on my laptop.↵
### Size 1000 Sorting....↵
Time taken by sortit() -> 1ms↵
Time taken by cpp sort() -> 0ms↵
↵
### Size 10000 Sorting....↵
Time taken by sortit() -> 2ms↵
Time taken by cpp sort() -> 1ms↵
↵
### Size 100000 Sorting....↵
Time taken by sortit() -> 9ms↵
Time taken by cpp sort() -> 15ms↵
↵
### Size 1000000 Sorting....↵
Time taken by sortit() -> 43ms↵
Time taken by cpp sort() -> 186ms↵
↵
### Size 10000000 Sorting....↵
Time taken by sortit() -> 331ms↵
Time taken by cpp sort() -> 2117ms↵
↵
### Size 100000000 Sorting....↵
Time taken by sortit() -> 3024ms↵
Time taken by cpp sort() -> 24147ms↵
↵
### Size 1000000000 Sorting....↵
Time taken by sortit() -> 50924ms↵
Time taken by cpp sort() -> 277987ms↵
↵
For higher values of n, it tends to become faster.↵
↵
If you find any similar or same algorithm, please let me know!↵
↵
↵
↵
↵
↵
