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

Tags:

Misc Example