Sorting Algorithms: Radix Sort
This week’s sorting algorithm is going to be a little different compared to the other sorting algorithms. With Radix Sort, we are not comparing two values based on: “is one greater than the other?”, instead we are sorting the data by: binary numbers and not by comparing elements.
Radix sort works on lists of numbers, or binary data, NOT by comparing elements. The more digits the bigger a number. And the way we sort with radix, is by sorting the numbers through 10 distinct buckets. These buckets are reused until we’ve gone through sorting the digits, and each bucket represents a number from 0–9 or base 10.
We organize the numbers in order, based on the value of the number in the 1s position first and then we iterate through the numbers again in the 10s, 100s and so on and so forth.
So if we were to sort the following list of numbers:
3, 92, 11, 214, 3160, 26, 817, 2000, 33
we first sort by the numbers in the one digits position first. So the numbers:
3, 92, 11, 214, 3160, 26, 817, 2000, 33 would be sorted into:
3160, 2000, 11, 92, 3, 33, 214, 26, 817
We are only looking at the single digit value, and not at the rest of the digits in the numbers. In the next run of our sort we will look at the values in the 10s place. And our next sorted list will be:
2000, 3, 11, 214, 817, 26, 33, 3160, 92
We’ll repeat this process for the hundreds and thousands until we arrive at our sorted list. If you notice in the image above, 3 gets sorted into the 0’s bucket. Because we’ve run out of digits for this number (3 does not have a digit in the 10s place) anything to the left of a number will be given an imaginary 0 value. This allows the number to hold its space in the sorted list. The number of times we go through this sorting process depends on the number of digits in the largest number. In this case, the largest number has 4 digits so we go through this process 4 times.
Hundreds:
2000, 3, 11, 26, 33, 92, 3160, 214, 817
Thousands:
3, 11, 26, 33, 92, 214, 817, 2000, 3160
So, how do we implement this into code?
Helper Methods (from Stack Overflow)
getDigit(number, place)
— returns the digit inside of the number at the given place value. So if our number is 365 and the place is 0 the digit is 5, if the place is 1 the digit is 6, and if the place is 2 the digit is 3.
function getDigit(number, place) {
return Math.floor(Math.abs(number) / Math.pow(10, place)) % 10;
}For example let’s say our number is 365, and place is 2. Math.abs(number) ensures that even if we were dealing with negative values, the number wouldn’t be returned as negative, so we are just dealing with absolute numbers. Math.pow(10, place) returns 10 to the place power or in this case 10 to the 2nd power. And we get 100. Then we Math.floor(365/100), which is 3. And lastly we find 3 % 10 which returns 3.
Looks like:
getDigit(365, 2)
Math.abs(365) => 365
Math.pow(10, 2) => 100
Math.floor(365/100) => 3
3%10 => 3
digitCount(number)
— this will return how many digits there are in the number. So if the number is 365, digitCount returns 3. We must include the edge case below if (num === 0) return 1 because if we run Math.log10(Math.abs(0)) the output would be-Infinity.
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}For example if our number is again 365, Math.log10(365) is 2.5622928644564746 and if we Math.floor(2.5622928644564746) the value it is 2. Lastly we add one, 2+1 and we get the length of our number, 3.
mostDigits(numbers)
— taking in a list of numbers, this method tells us what is the size of the largest number in the list. If these were our numbers, [1000, 1786300, 365], most Digits would return 7.
function mostDigits(nums) {
let maxDigits = 0;
for (let num of nums) {
maxDigits = Math.max(maxDigits, digitCount(num));
}
return maxDigits;
}For example, let’s say mostDigits takes in this number list: [1000, 1786300, 365]. First we declare a variable maxDigits equal to 0. We are going through each number of the list of numbers or num of nums to compare the digit length and assign the max value to the maxDigits variable. Under the hood this looks like:
1. maxDigits = Math.max(0, digitCount(1000))
which is greater, 0 or 4? => maxDigit = 4
2. maxDigits = Math.max(4, digitCount(1786300))
which is greater, 4 or 7? => maxDigit = 7
3. maxDigits = Math.max(7, digitCount(365))
which is greater, 7 or 3? => maxDigit = 7
Return 7
Implementation of Radix Sort…
- Our function will take in a list of numbers
- Find the max digits of the largest number in the list of numbers
- Create a loop with a variable k starting at 0 and going up to the value of max digits from the largest number.
• where inside each loop we create buckets for each digit (0–9)
• And place each number in the correct bucket based on the index of k for that number (ie. 0 is the ones, 1 is the 10s, 2 is the 100s, etc.). - Replace our existing array with values from the buckets from 0 to 9
- Lastly, return the sorted number list.
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;
}Let’s break this down (full code snippet below):
First: We take in a list of numbers, and declare a variable maxDigitCount which is the length of the largest number in the list.
Example numbers: [90, 881, 16, 320722, 531, 5, 91, 4760]
maxDigitCount = 6, because 320722 is the largest number and there are 6 digits within it.
Second: Then inside a loop, we declare variable k which represents the place of the number(1s, 10s, 100s, 1000s)
Inside the k loop we declare a variable called digitBuckets, and inside this variable, we create a hash of 10 empty arrays ([]).
Third: We create a nested loop with variable i which represents the current number in the list that we are iterating through in this case we start at 0 out of 8 numbers. While i is less than the length of the list of numbers(8), we will increment i.
Fourth: Inside the nested i loop, we declare variable digit = getDigit(nums[i], k) and then based on the digit, we push the number into the digitBucket, with digitBuckets[digit].push(nums[i]).
Example: First iteration of i:
digit = getDigit(nums[0], k=0)
nums[0] = 90
digit = 0
digitBuckets[0].push(90)
Example: Second iteration of i:
digit = getDigit(nums[1], k=0)
nums[1] = 881
digit = 1
digitBuckets[1].push(881)
Example: Third iteration of i:
digit = getDigit(nums[2], k=0)
nums[2] = 16
digit = 6
digitBuckets[6].push(16)
Fifth: Once we complete the nested loop, we reassign the value of nums into a new array, concatenating the numbers in order from digitBuckets.
Example: First iteration of k:
nums = [90, 881, 16, 320722, 531, 5, 91, 4760]
digitBuckets = {
0: [90, 4760],
1: [881,531, 91],
2: [320722],
3: [],
4: [],
5: [5],
6: [16],
7: [],
8: [],
9: []
}
nums = [].concat(…digitBuckets)
=> [90, 4760, 881, 531, 91, 320722, 5, 16]
Final Step: we repeat all previous steps, until k is no longer less than maxDigitCount, and lastly we return the sorted list of numbers.
function getDigit(number, place) {
return Math.floor(Math.abs(number) / Math.pow(10, place)) % 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 num of nums) {
maxDigits = Math.max(maxDigits, digitCount(num));
}
return maxDigits;
}
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;
}