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
- Outer loop ends at MaxNumOfDigits
- First, create 2 helper functions
- 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;
}
Top comments (0)