6. Radix Sort.md

Radix Sort

Radix Sort is a non-comparative sorting algorithm. Unlike the previous sorting algorithms, it avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, Radix Sort has also been called Bucket Sort and Digital Sort.

Radix Sort can be implemented to start at either the Most Significant Digit (MSD) or Least Significant Digit (LSD). For example, with 1234, one could start with 1 (MSD) or 4 (LSD).

For this exercise, Radix Sort will be implemented using the Least Significant Digit.

LSD Radix Sorts typically use the following sorting order: short keys come before longer keys, and then keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, like the sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. LSD sorts are generally stable sorts.

MSD Radix Sorts are most suitable for sorting strings or fixed-length integer representations. A sequence like ["b", "c", "e", "d", "f", "g", "ba"] would be sorted as ["b", "ba", "c", "d", "e", "f", "g"]. If lexicographic ordering is used to sort variable-length integers in base 10, then numbers from 1 to 10 would be output as [1, 10, 2, 3, 4, 5, 6, 7, 8, 9], as if the shorter keys were left-justified and padded on the right with blank characters to make the shorter keys as long as the longest key. MSD sorts are not necessarily stable if the original ordering of duplicate keys must always be maintained.

Other than the traversal order, MSD and LSD sorts differ in their handling of variable length input. LSD sorts can group by length, radix sort each group, then concatenate the groups in size order. MSD sorts must effectively 'extend' all shorter keys to the size of the largest key and sort them accordingly, which can be more complicated than the grouping required by LSD.

However, MSD sorts are more amenable to subdivision and recursion. Each bucket created by an MSD step can itself be radix sorted using the next most significant digit, without reference to any other buckets created in the previous step. Once the last digit is reached, concatenating the buckets is all that is required to complete the sort.

Time and Space Complexity

• The lower bound for the previous comparative sorting algorithm (Merge Sort, Heap Sort, Quick-Sort .. etc) is Ω(n * logn), i.e., they cannot do better than n * logn.
• Radix sort operates in O(kn) time, where n is the number of items in the array, and k is the number of digits of the largest item.
• Radix Sort has an auxillary space complexity of O(n + k), where n is the number of items in the array, and k is the number of digits of the largest item.

Exercise

1. Write a function called getDigit that accepts a number and a place value. The function should return the number's digit at the given place value.
2. Write a function called digitCount that accepts a number input, and returns the number of digits in the input.
3. Write a function called mostDigits that accepts an array of numbers, and returns the number of digits in the largest number in the array.
4. Write a function called radixSort that takes an array of numbers, and returns the sorted array with all the numbers sorted from smallest to largest. Additionally, you should be able to see how numbers in the array gets sorted based on their digits.

Examples:

• Get Digit Helper

  • getDigit(12345, 0) // 5
  • getDigit(12345, 2) // 3
  • getDigit(12345, 6) // 0

• Digit Count Helper

  • digitCount(1) //1
  • digitCount(123) //3
  • digitCount(12345) //5

• Most Digits Helper

  • mostDigits([1234, 56, 7]) // 4
  • mostDigits([1, 11, 11111, 111]) // 5
  • mostDigits([12, 34, 56, 78]) // 2

• Radix Sort

  • radixSort([4,5,2,4,5,1,3,5,4,5,3,5,3,2,4]) // [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]

  • radixSort([3221,1,10,9680,577,9420,7,5622,4793,2030,3138,82,2599,743,4127])
    // [1,7,10,82,577,743,2030,2599,3138,3221,4127,4793,5622,9420,9680]

Note: You should also see the status of the array after each pass in the console!

---

Solution

Get Digit Helper

function getDigit(num, place) {
  //  Keep dividing by 10 (base) until we reach our desired digit,
  //  then use modulo operator to get only the digit that we want
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

Digit Count Helper

function digitCount(num) {
  //* Log base 10 (Math.log10) helps us get the number we want!
  //! However, we need to add a special case for when
  //! the input number is 0, because log(0) is undefined.
  if(num === 0) return 1;
  //  Otherwise, just floor the log10 output and add 1 to get
  //  the number of digits for a base 10 number!
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

Most Digits Helper

function mostDigits(arr) {
  //  Simply use a reducer to loop over the input array,
  //  and get the largest number of digits!
  return arr.reduce((acc,nxt) => acc > digitCount(nxt) ? acc : digitCount(nxt), 0);
}

Radix Sort

function radixSort(arr) {
  //  Get the largest number of digits in the array
  const radix = mostDigits(arr);
  //  Start a loop according to the largest number of digits
  for(let n = 0; n < radix; n++) {
    //  Create a bucket for each digit (0 to 9)
    const buckets = Array.from({length: 10}, () => []);
    //  Loop over the input array
    for(let i = 0; i < arr.length; i++) {
      //  For each number, get the current digit to look at
      let currentDigit = getDigit(arr[i], n);
      //  Place the current number into the bucket according to
      //  its current digit that we're currently looking at
      buckets[currentDigit].push(arr[i]);
    }
    //  Spread the bucket contents into a new array
    arr = [].concat(...buckets);
  }
  //  Return sorted array
  return arr;
}

References

Wikipedia - Radix Sort

GeeksforGeeks - Radix Sort