JavaScript Sorting Algorithms Explained: Radix Sort -

Today in our JavaScript Sorting Algorithm series we talk about Radix Sort.

All of the sorting algorithms mentioned in this series so far were Comparison Sorts, meaning that they take two items, they do some comparisons and they return the bigger of those two numbers. Another type of sorts are Integer Sorts, which take advantage of the fact that integers (numbers) have special properties that the algorithm can make use of.

Introduction to Radix Sort

So what is the Radix Sort? Radix Sort is an integer sorting algorithm that only works with numbers (or data types that can be represented by numbers), and it doesn’t compare elements, but takes advantage of the digits that the number itself contains. The algorithm creates ‘buckets’ ranging from 0 to 9 (in a decimal system) that will help us sort the array. We group the numbers based on individual digits sharing the same significant position and value. Radix sort runs faster than the O(n log n) of Merge and Quick sort and actually can perform in linear time.

Visualization

The Inputs for this algorithm are: [3221, 1, 10, 577, 9420, 7, 4793, 2030, 3138, 82, 2599, 743].

Radix Sort Vizualized — Radix Sort Visualized. Check visualgo.net for more sortinig algorithms.

Each iteration sorts the numbers going from the least significant to the most significant and it groups them by digit. The first iteration groups numbers that have zero as the last digit together with other numbers that have zero as the last digit, and they come before numbers that have one as the last digit, and those that have one as the last digit come before those that have two, and so on. After the first iteration, we repeat the logic, only this time using the second-from-right digit to group the numbers. And the process continues. The number that has the biggest digit count dictates how many loops will be run, if our biggest number has four digits, then we will repeat the loop four times!

Radix Sort first iteration — First Iteration of the Radix Sort

Radix Sort implementation

Before we write the Radix Sort implementation, we need some helper methods. We need to write some logic to get the digit at a given place. Down below you can see our test cases.

getDigitAtPlace(9420, 2); // 4
getDigitAtPlace(95959, 0); // 9
getDigitAtPlace(28531, 4); // 2
getDigitAtPlace(123, 4); // 0

There are a couple of possible variations to achieve this. We could modulo the number by an exponential 10 value (using math) or we can play with string transformations, among other possibilities. The complete solution for this method is written below. The method will transform the number to a string, and then to a reversed array in which case we can simply pluck our value.

function getDigitAtPlace(num, i) {
  return num.toString().split("").reverse()[i] || 0;
}

getDigitAtPlace(9420, 2); 
// 9420 (Number) => 
// "9420" (String) => 
// ["9", "4", "2", "0"] (Array) => 
// ["0", "2", "4", "9"] (reversed) => 
// 4 (the second indexed item - our return value)

The other helper method searches for the item with the most digits. As mentioned above, we need to know this information in order to tell our algorithm how many times it should run the sorting logic.

getBiggestDigitCount([9420, 12, 555]); // 4
getBiggestDigitCount([123, 12678, 1]); // 5

To do this we take our number array as an input, and then we iterate through it, checking on every iteration whether the current number is longer than the one we stored in our maxDigits variable, that actually stores the number with the biggest digit count currently.

function getBiggestDigitCount(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, nums[i].toString().length);
  }

  return maxDigits;
}

getBiggestDigitCount([9420, 12, 555]);
// 1st iteration -> maxDigits is 0, the current digit count for 9420 is 4, maxDigits becomes 4
// 2nd iteration -> maxDigits is 4, the current digit count for 12 is 2, maxDigits stays 4
// 3rd iteration -> maxDigits is 4, the current digit count for 555 is 3, maxDigits stays 4
// method returns 4

Radix Sort Pseudocode and Implementation

The algorithm should get the largest digit number in order to get the loop count
The algorithm should loop from 0 to the loop count (largest digit count)
In every iteration, the algorithm should create buckets ranging from 0-9 and place each number in the corresponding bucket
The bucket numbers ordered by the digit should become the new array
The algorithm should repeat the process until the loop is done executing
The algorithm should return the list

function radixSort(nums) {
  let maxDigits = getBiggestDigitCount(nums);
  for (let i = 0; i < maxDigits; i++) {
    let bucketArray = Array.from({ length: 10 }, () => []);
    for (let j = 0; j < nums.length; j++) {
        let digit = getDigitAtPlace(nums[j], i);
        bucketArray[digit].push(nums[j]);
    }

    nums = [].concat(...bucketArray);
  }
}

radixSort([3221, 1, 10, 577, 9420, 7, 4793, 2030, 3138, 82, 2599, 743]);

Initially, we store the biggest digit count in our maxDigits variable. Then we write a for loop that will have maxDigits number of iterations. Inside every iteration, we create a bucketArray that will group our values positioned by their digit. We start a new loop, this time looping through the input array and for each iteration we pluck a digit, starting from the least-significant and we push the number inside the appropriate bucket. After we grouped all of our numbers, we replace the nums array with the bucketArray.

Big O complexity

Radix sort is actually quite efficient, and it runs on average in O(nl) time, where n is the size of the input data and l is the number of digits of the longest number. Radix sort can actually be optimized to be extremely fast when dealing with appropriate data – and benchmarks have shown that it is faster than other general-purpose sorting algorithms by more than 50%!

Conclusion

Radix sort is different from other sorting algorithms because it sorts data lexicographically. Therefore, it is specific in its own way and specialized to be best used with numbers. When dealing with different types of data – it might be better to use some Divide-and-Conquer algorithms.

Additionally, if you want to check up on other sorting algorithms you can do it by clicking on any of the following links.

Facebook Tweet Pin LinkedIn