Radix Sort is a code example
Example 1: radix sort
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10,i)) % 10
}
function digitCount(num) {
if(num === 0 ) return 1
return Math.floor(Math.log10(Math.abs(num))) + 1
}
function mostDigitCount(nums) {
let maxDigit = 0
for(let i = 0;i< nums.length;i++) {
maxDigit = Math.max(maxDigit, digitCount(nums[i]))
}
return maxDigit
}
function Radix(nums){
let maxDigitCount = mostDigitCount(nums)
for(let k=0; k< maxDigitCount; k++) {
let digitbucket = Array.from({length:10} , () => [])
for(let i=0; i< nums.length; i++) {
let digit = getDigit(nums[i], k)
digitbucket[digit].push(nums[i])
}
nums = [].concat(...digitbucket)
}
return nums
}
console.log(Radix([23,123, 23333,444444,55555555]))
Example 2: radix sort
//Code by Soumyadeep
//insta id: @soumyadepp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int maxElement(vector<int> arr)
{
int m = arr[0];
for (int i = 0; i < arr.size(); i++)
{
if (arr[i] > m)
m = arr[i];
}
return m;
}
int digitCnt(int x)
{
int z = x;
int c = 1;
while (z)
{
z /= 10;
c++;
}
return c;
}
void radixSort(vector<int> &arr)
{
int x = maxElement(arr); //O(N)
int countDigits = digitCnt(x); //O(numberofdigitsinx)
for (int i = 1; i <= countDigits; i++) //runs number of digits in maximum element in the array
{
vector<int> holder[10];
for (int j = 0; j < arr.size(); j++) //O(N)
{
int m = i;
int k;
int p = arr[j];
while (m) //O(logN)
{
k = p % 10;
p /= 10;
m--;
}
holder[k].push_back(arr[j]);
}
arr.clear();
for (int c = 0; c < 10; c++)
{
arr.insert(arr.end(), holder[c].begin(), holder[c].end());
}
}
//approx O(ND)
}
int main()
{
int t;
cin >> t;
while (t--)
{
vector<int> arr;
int n, x;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
arr.push_back(x);
}
radixSort(arr);
cout << "The sorted array is " << endl;
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
}
return 0;
}