radix algorithm 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 pseudocode
Radix-Sort(A, d)
for j = 1 to d do
int count[10] = {0};
for i = 0 to n do
count[key of(A[i]) in pass j]++
for k = 1 to 10 do
count[k] = count[k] + count[k-1]
for i = n-1 downto 0 do
result[ count[key of(A[i])] ] = A[j]
count[key of(A[i])]--
for i=0 to n do
A[i] = result[i]
end for(j)
end func