Radix Sort Algorithm Implementation in JavaScript

Use Case:

The Radix Sorting Algorithm is an interesting program that puts integers in order by breaking up integers into their individual places - think 1s place, 10s place, 100s place and so on in decimal.

Here's a description from Wikipedia:

Below is how we can implement the Radix Sort in JavaScript.

1. Get Max Length of Integers

The first thing we need to do is create a function that will scan our dataset and give us the largest number in terms of how many places (e.g. 1s, 10s, 100s) it contains.

getMax = array => { // O(n)
	let max = 0
	for (let num of array) {
		max = (max < num.toString().length) ? num.toString().length : max
	}
	return max
}

This getMax function will accept an array and return the maximum value discovered. It'll find this by looping through the entire array dataset (thus, linear time - O(n)) and determining if the current data value, when translated to a string (to find the length in JavaScript) is longer than the maximum length found up until that point. If it is than it will replace the current max with its length and continue the loop.

2. Get Value at Position in Integer

We need a second helper function that will help us to return the number in the integer in the current place we're comparing.

getPosition = (num,place) => Math.floor(num / Math.pow(10,place)) % 10 // O(1)

The getPosition function accepts a number and a place and performs some math to find the value of the integer in position of place. We're using 2 native JavaScript functions - Math.pow gives us the result of the base to the exponent power. In this case, it would be 10 to the place power. That number will be divided into 2 and the Math.floor function will round the resulting value down to a whole number. Lastly, we'll take that rounded-down number modulo 10 (the remaining value after dividing it by 10) and return it from our getPosition function.

This was definitely the trickiest part of our algorithm so far but that's only because we're dealing with math that isn't found in other algorithm implementations.

3. Radix Sort Function

Now we can take advantage of the 2 prior functions and loop through our dataset.

radixSort = array => { // O(nk)
	var max = getMax(array)
	for (let i = 0; i < max; i++) {
		let buckets = Array.from({length:10}, () => [])
		for (let j = 0; j < array.length; j++) {
			buckets[getPosition(array[j], i)].push(array[j])
		}
		array = [].concat(...buckets)
	}
	return array
}

We start off the radixSort function by getting the max value (length of longest number) of our dataset. Then we'll perform a few loops until we've looped as many times as the max number result was.

While we're looping, we'll create 10 buckets to represent each possible place value from 0-9. We'll need these buckets to hold our relevant data.

Then we'll loop through every value in our dataset and push the data into the bucket if its returned position matches the bucket's index. After we do that for every value, we'll update our array with the result from the buckets and then return the array.

var array = [8,3,5,9,1,5,9,2,3,8,4]
radixSort(array)
// 8
// 3,8
// 3,5,8
// 3,5,8,9
// 1,3,5,8,9
// 1,3,5,5,8,9
// 1,3,5,5,8,9,9
// 1,2,3,5,5,8,9,9
// 1,2,3,3,5,5,8,9,9
// 1,2,3,3,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9

As far as efficiency is concerned, the time complexity of the Radix Sort algorithm is O(nk) where n is the size of the dataset and k is the number of places of the largest number (max). Space complexity is quite a bit worse than many algorithms as it is O(n + k) because we're duplicating our dataset into buckets for each possible place value.

Check out other sorting algorithm implementations in JavaScript:

• Merge Sort
• Selection Sort
• Shell Sort
• Bubble Sort
• Heap Sort
• Insertion Sort
• Quick Sort