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. **UPD**- Added radix sort comparison also!↵
↵
### Size 1000 Sorting....↵
↵
Time taken by sortit() -> 1ms↵
Time taken by cpp sort() -> 0ms↵
Time taken by radix sort(base 256)(4 rounds) -> 0ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 4ms↵
↵
↵
### Size 10000 Sorting....↵
↵
Time taken by sortit() ->21ms↵
Time taken by cpp sort() -> 1ms↵
Time taken by radix sort(base 256)(4 rounds) -> 1ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 5ms↵
↵
### Size 100000 Sorting....↵
↵
Time taken by sortit() -> 9ms↵
Time taken by cpp sort() -> 15ms↵
Time taken by radix sort(base 256)(4 rounds) -> 5ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 18ms↵
↵
### Size 1000000 Sorting....↵
↵
Time taken by sortit() -> 430ms↵
Time taken by cpp sort() -> 1865ms↵
Time taken by radix sort(base 256)(4 rounds) -> 54ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 90ms↵
↵
### Size 10000000 Sorting....↵
↵
Time taken by sortit() -> 33116ms↵
Time taken by cpp sort() -> 2171ms↵
Time taken by radix sort(base 256)(4 rounds) -> 572ms↵
Time taken by cppradix sort(base 1 << 16)(2 rounds) -> 2117508ms↵
↵
### Size 100000000 Sorting....↵
↵
Time taken by sortit() -> 302456ms↵
Time taken by cpp sort() -> 241479ms↵
Time taken by radix sort(base 256)(4 rounds) -> 5747ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 4749ms↵
↵
### Size 1000000000 Sorting....↵
Time taken by sortit() -> 35092471ms↵
Time taken by cpp sort() -> 277987ms↵
Time taken by radix sort(base 256)(4 rounds) -> 65696ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 50732ms↵
↵
For higher values of n, it tends to become faster. Hence, this is suitable for higher n values.↵
↵
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. **UPD**- Added radix sort comparison also!↵
↵
### Size 1000 Sorting....↵
↵
Time taken by sortit() -> 1ms↵
Time taken by cpp sort() -> 0ms↵
Time taken by radix sort(base 256)(4 rounds) -> 0ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 4ms↵
↵
↵
### Size 10000 Sorting....↵
↵
Time taken by sortit() ->
Time taken by cpp sort() -> 1ms↵
Time taken by radix sort(base 256)(4 rounds) -> 1ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 5ms↵
↵
### Size 100000 Sorting....↵
↵
Time taken by sortit() -> 9ms↵
Time taken by cpp sort() -> 15ms↵
Time taken by radix sort(base 256)(4 rounds) -> 5ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 18ms↵
↵
### Size 1000000 Sorting....↵
↵
Time taken by sortit() -> 4
Time taken by cpp sort() -> 18
Time taken by radix sort(base 256)(4 rounds) -> 54ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 90ms↵
↵
### Size 10000000 Sorting....↵
↵
Time taken by sortit() -> 3
Time taken by cpp sort() -> 2171ms↵
Time taken by radix sort(base 256)(4 rounds) -> 572ms↵
Time taken
↵
### Size 100000000 Sorting....↵
↵
Time taken by sortit() -> 30
Time taken by cpp sort() -> 2414
Time taken by radix sort(base 256)(4 rounds) -> 5747ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 4749ms↵
↵
### Size 1000000000 Sorting....↵
Time taken by sortit() -> 350
Time taken by cpp sort() -> 277987ms↵
Time taken by radix sort(base 256)(4 rounds) -> 65696ms↵
Time taken by radix sort(base 1 << 16)(2 rounds) -> 50732ms↵
↵
For higher values of n, it tends to become faster. Hence, this is suitable for higher n values.↵
↵
If you find any similar or same algorithm, please let me know!↵
↵
↵
↵
↵
↵
