Radix Sort

What do we understand about Radix Sort ?

• Stable Sorting Algorithm
• Mutates original Array
• Is NOT a comparison sort
• sorts by exploiting the way numerics are interpreted
• mostly implemented if Array contains only positive numbers
  • there can only exist 10 different positive integers (0 - 9)
• each loop results in Array<Array<Int>>
  • similar concept to Bucket Sort
• uses 2 nested for-loops
  • First, create 2 helper functions
    • getMaxNumOfDigits()
    • getDigitByPos()
  • Next, in main function
    • Outer loop ends at MaxNumOfDigits
      • init new bucket of 10 on each loop (Array of size 10)
    • Inner loop loops thru total number of elements in the Array
      • bucket position would have an Array inside pushed with values of that digit by position
    • flatten the Array of Array and reassign back to original Array
• Time and Space Complexities are a complete opposite of Counting Sort
• Time complexity
  • Best is O(nk)
  • Average is O(nk)
  • Worst is O(nk)
• Space complexity
  • O(n+k)

function getMaxNumOfDigits(arr) { const max = Math.max(...arr); if (max === 0) return 1; // suggest to just memorise this if can't think of the math on the spot // else just use stringify and get length of string return Math.floor(Math.log10(max)) + 1; } function getDigitByPos(num, pos) { if (num === 0) return 0; // e.g. // num = 1234, pos = 2 // floor(1234 / 10^2) % 10 // floor(1234 / 100) % 10 // = 12 % 10 // = 2 return Math.floor(num / Math.pow(10, pos)) % 10; } function RadixSort(arr) { const arrLength = arr.length; const maxNumOfDigits = getMaxNumOfDigits(arr); for(let i = 0; i < maxNumOfDigits; i++) { const digitsBucket = new Array(10); for (let j = 0; j < arrLength; j++) { const digit = getDigitByPos(arr[j], i); if (!digitsBucket[digit]) { digitsBucket[digit] = []; } digitsBucket[digit].push(arr[j]); } arr = digitsBucket.flat(); } return arr; }