DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on

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;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)