JavaScript Radix Sort

Sorting is an important part of programming and usually the runtime will be O(n log (n)) or O(n2) but there is a way to improve the performance when we deal with Numbers.

Sort algorithms are by comparison ( less or greater). Radix is a non-comparative sorting algorithm and exploits the fact that information about the size of a number is encoded in the numbers of digits likely more digits means a bigger number!

How does it Work ?

We have a list of numbers and we create 10 different buckets and they represent all the possible single digit number.

1556 we check the first digit from the right 6

We go through the list and for each item we look at the first digit from the right side and we group them in the right bucket based on this number.

the first digit from the right of 902 is 2 so it goes in the 2 bucket.

then we reform the list and keep it in a new array.

Then we repeat the same process except we look at next digit to the left.

the 2nd digit form the right of 408 is 0 (goes to the 0 bucket). 7 as no 2nd digit so we put in the 0 bucket as well.

We repeat the process based on how many digits is in the largest number of the list.

Radix Sort: Implementation

in Order to implement the function we will need 2 Helper Methods

1-getDigit, return the digit in num at the given place value.

getDigit(439, 0); // 9
getDigit(439, 1); // 3
getDigit(439, 2); // 4
function getDigit(num, i) {
  return Math.floor(num / Math.pow(10, i)) % 10;
 // %10 give you the last digit of a number 239347% 10 => 7
 // if i = 0 , Math.pow(10,0) => 1 
    // i = 1, Math.pow(10,1) => 10 
// 239347/10 => 23934.7
    //Math.floor(23934.7) => 23934
       // 23934 %10 = 4
}
getDigit(239347, 2); // 3

2- digitIteration, we need to know how many times we are going to iterate and it is equal to the length of the biggest number

digitIteration(12); // 2
digitIteration(112233); // 6

function digitIteration(num) {
  const biggestDigit = Math.max(...num)
// find the largest digit in the array (2345)
return Math.floor(Math.log10(biggestDigit)) + 1;
// Math.log10(2345) //3.370142847051102
// Math.floor(3.370142847051102) 3 +1//4
}
digitIteration([12,2345,1,45]) // 4

Radix sort using the helper Methods

function radixSort(nums){
    let iteration = digitIteration(nums)
    // store the number of iterations
for(let k = 0; k < iteration; k++){
// loop until the biggest digit is done
        
let digitBuckets = Array.from({length: 10}, () => []);
// create an array of 10 empty array
        for(let i = 0; i < nums.length; i++){
        // loop through the array we are going to sort
          let digit = getDigit(nums[i],k);
         //digit give us the last digit of our number from the right
         // getDigit(2345,0) => 5 
digitBuckets[digit].push(nums[i]);
  // we use digit for the index and push the number in the new array
  // 2345 digit = 5 
digitBuckets =|     |    |    |    |    | 2345 |    |    |    |    |
                 0     1    2    3    4    5      6   7     8    9  
        }
        nums = [].concat(...digitBuckets);
// we concat on an empty array using the spread operator to not return an array of array

    }
    return nums;
    // FINALLY ^u^

}
radixSort([12,2345,1,45]) // [ 1, 12, 45, 2345 ]

Finally we get this :

function getDigit(num, i) {
  return Math.floor(num / Math.pow(10, i)) % 10;
}
function digitIteration(num) {
  const biggestDigit = Math.max(...num)
  return Math.floor(Math.log10(biggestDigit)) + 1;
}
function radixSort(nums){
  let iteration = digitIteration(nums)
  for(let k = 0; k < iteration; k++){
    let digitBuckets = Array.from({length: 10}, () => []);
    for(let i = 0; i < nums.length; i++){
        let digit = getDigit(nums[i],k);
        digitBuckets[digit].push(nums[i]);
    }
    nums = [].concat(...digitBuckets);
  }
  return nums;
}
radixSort([12,2345,1,45]) // [ 1, 12, 45, 2345 ]

Time Complexity O(nk)

Space Complexity O(n+k)

n = length of array, k= number of digits