Radix Sort Data Structures & Algorithms #13

Hello.. Today is my birthday and we will look at Radis Sort , I hope that finds you well.

Radis Sort, seems to be one of the controversial one but definitely a much quicker one for that matter, it has a linear O(n) time complexity that’s why there is a need for you to know about it. either you will use it in any of your projects or not it’s still worth knowing it. Radis sort Algorithm has an interesting way of sorting not using any of the methods we have in the previous types ie. divide and conquer, recursion or swapping but rather it counts and groups it’s elements in their respective digit base in ascending / descending order. let’s say in base 10 number system we have each digit of a number having a value ranging from 0-9 so we classify all elements according to each digits they carry in their existence.  Think of it to have an array of numbers to be sorted then you have a scheme down in base 10 to arrange the numbers based on their individual sub-numbers, at each level they arrange themselves based on the nth number of reference, so let’s say you throw all the numbers into the scheme to arrange itself for the first time stating from their last digits it will return a container of numbers ranging from 0-9 with well arranged grouped numbers of the same last digits on a scale of 0-9 (base 10) then we move to the next number from the back, again throw the numbers back to the container for the arrangement based on the second number from the back. let’s look at it now.

Assuming you have [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127] to be sorted. first throw the numbers into the base10  Bucket / Container ie. I call it the Magic Container :). Remember the scale of the partition of the container is from 0-9 like this |0||1||2||3||4||5||6||7||7||9|. for the first time we should have under 0=|10, 9680, 9420, 2030|     under 1=|3221, 1|      under 2=|5622, 82|  under 3=|4793, 743|  under 4=|    …|  under 5=|…|  under 6=|…|    under 7=|577, 7, 4127|  under 8=|3138|  under 2=|2599|  I hope the point is clear here, so then we throw them back to line up from the ascending or descending order depending on the interest and this time round we get back [10, 9680, 9420, 2030,3221, 1 ,5622, 82  ,4793, 743,577, 7, 4127,3138,2599] Notice the original unsorted array didn’t start with 10 or ended with 2599 but rather 3221 and 4127.  again we throw the partially sorted result above back into our Magic Container for the second round but this time starting from the second element from the back. After sorting all the second numbers of the individual elements send them back to the array form and repeat the same until you reach the end of the greatest number.  ie. the greatest number should obviously be the one with the most numbers in it’s existence. doing this will eventually sort your records, you see ! how hard was that ? easy i guess ! now let’s represent this in a coding format.

In Radix Sort we need some helper functions to facilitate the algorithm and JavaScript doesn’t come with any of that so we need to get down to the mad and doing it the only way the hard way.

the helper functions are as follows getDigit, digitCount, mostDigits. 

 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 mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

With these three function we should be ready to get our Radix Sort Started, basically they are just based on our concepts above where the computer needs to determine the nth digit of the element and count it’s occurrence in memory without forgetting to hold the highest Digits for the next grouping.

function radixSort(nums){
  let maxDigitCount = mostDigits(nums);
  for(let k = 0; k < maxDigitCount; 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([23,345,5467,12,2345,9852])

Ladies and Gentlemen behold Radix sort for you. create a Bucket or Container (Magic Container) for each digit 0-9 and group each element into their respective slot based on the current nth digit  of the element.

The End… All the Best.