Data Structures and Algorithms - Radix Sort

The previous two intermediate sorting algorithms that I "learned" were comparison sorts. We compared values and swapped them, at the most basic level. And now that I think about it this is the case for the elementary sorts as well. The one thing to remember is the best time complexity that we can achieve with these comparison sorts is logarithmic, which is not horrible but we'd like to do even better, and this is where Radix Sort comes in. One thing to note is Radix Sort and other non comparison sorts will not guarantee a better time complexity than the other sorting algorithms, just in specific cases they are much more efficient. Radix Sort is a special sorting algorithm that works on lists of numbers, usually binary. We could actually convert a list of strings to integers and then use the Radix Sort but at that point you'd be better off selecting a different type. The way that this algorithm works is by exploiting the fact that the information about the size of a number is encoded in the number of digits. What exactly does that mean though?

Well if a number has more digits its a larger number. 300 has 3 digits (3,0,0) where 95, has two digits (9,5) so we can safely assume based on digits that 300 is larger than 95 and also because we just know that lol. The way this works (and this is for base 10 numbers, no decimals, for now) is we have 10 "buckets" 0-9, and we place numbers in each bucket based on their last (right most) digit. We do not sort in within the bucket rather just place them there. We then place them back into a list based on their bucket order, so even though 9 is smaller than 1000, 1000 would be first based on it's right most digit is 0. The process is then repeated based now on the second digit from the right. Any number that does not have a second digit from the right, say 9 would be put in the 0 bucket since its second digit from right is 0. We continue to repeat this process until we have hit the largest most value. The number of times we repeat this process is by the number of the largest digit number.

. Here is an example that kinda shows you what is going on.

To implement Radix Sort we have to write a few helper functions, just as we did before, wether that be pivot, swap, merge, etc... One helper function we'll need to write is a method that returns the digit in the number at a give place. so lets say we have getDigit(number, place) we'd expect the following results:

getDigit(93824, 0);  //4
getDigit(93824, 1);  //2
getDigit(93824, 2);  //8
getDigit(93824, 3);  //3
getDigit(93824, 4);  //9

Hint hint for this one there is no reason to reinvent the wheel. Stackoverflow has many solutions and here is one of them:

function getDigit(number, place) {
    return Math.floor(Math.abs(number) / Math.pow(10, place)) % 10;
}

The next helper method we'll need to create is how many digits are in the numbers. Why? Well because the largest one will be how we determine just how many times to sort into buckets / reorder. We'll call this digitCount(number) and we'll get some more great code from Stackoverflow and get:

function digitCount(number) {
    if(number === 0) return 1;
    return Math.floor(Math.log10(Math.abs(number))) + 1;
}

Our final method to create is one that given an array of numbers return the largest digitCount in that array, and as you can see we'll use our previously defined method. By using Math.max(num1, num2) we can compare and return our max value. Here we go:

function mostDigits(numbers) {
    let maxDigits = 0;
    for(let i = 0; i < numbers.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(numbers[i]));
    }
    return maxDigits;
}

For the actual Radix Sort we'll need to:

1. Find the largest digits (mostDigits())
2. Start a loop from 0 until the return of the previous step
3. create buckets for each digit, which is an array with 10 sub arrays each starting empty.
4. place each number in the proper corresponding bucket based on whichever "digit" we are comparing (we'll be using 'getDigit()` here).
5. Replace our array (reorder) with the values from the buckets from 0 -> 9
6. return a list (all sorted woot woot!!!!) Radix Sort.