Radix Sort Algorithm in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Radix Sort on a small array

What is the output of the following JavaScript code that uses Radix Sort to sort an array of positive integers?

DSA Javascript

function radixSort(arr) {
  const maxNum = Math.max(...arr);
  let digit = 1;
  while (parseInt(maxNum / digit) > 0) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let num of arr) {
      let digitNum = parseInt((num / digit) % 10);
      buckets[digitNum].push(num);
    }
    arr = [].concat(...buckets);
    digit *= 10;
  }
  return arr;
}

const input = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(input));

A [24, 2, 45, 66, 75, 90, 170, 802]

B [802, 170, 90, 75, 66, 45, 24, 2]

C [2, 24, 45, 66, 75, 90, 170, 802]

D [2, 24, 45, 66, 75, 170, 90, 802]

💡 Hint

Think about how Radix Sort sorts numbers digit by digit from least significant to most significant.

Radix Sort sorts numbers starting from the least significant digit to the most significant digit using buckets for each digit (0-9). After processing all digits, the array is sorted in ascending order.

🧠 Conceptual

intermediate

Understanding Radix Sort Buckets

In Radix Sort, what is the purpose of using buckets during each digit iteration?

A To reverse the array after sorting each digit.

B To group numbers based on the current digit being processed, so they can be collected in order.

C To store the final sorted array after all digits are processed.

D To count how many times each digit appears in the array.

💡 Hint

Think about how numbers are grouped by digits before combining them back.

Buckets group numbers by their current digit so that when combined, the order respects that digit's sorting, enabling stable sorting digit by digit.

❓ Predict Output

advanced

Radix Sort with Negative Numbers

What will be the output of this modified Radix Sort code when sorting an array containing negative and positive integers?

DSA Javascript

function radixSortWithNegatives(arr) {
  const positives = arr.filter(x => x >= 0);
  const negatives = arr.filter(x => x < 0).map(x => Math.abs(x));

  function sort(nums) {
    const maxNum = Math.max(...nums);
    let digit = 1;
    while (parseInt(maxNum / digit) > 0) {
      let buckets = Array.from({ length: 10 }, () => []);
      for (let num of nums) {
        let digitNum = parseInt((num / digit) % 10);
        buckets[digitNum].push(num);
      }
      nums = [].concat(...buckets);
      digit *= 10;
    }
    return nums;
  }

  const sortedPositives = sort(positives);
  const sortedNegatives = sort(negatives).map(x => -x).reverse();

  return [...sortedNegatives, ...sortedPositives];
}

const input = [170, -45, 75, -90, 802, 24, -2, 66];
console.log(radixSortWithNegatives(input));

A [-90, -45, -2, 24, 66, 75, 170, 802]

B [-90, -45, -2, 802, 170, 75, 66, 24]

C [-2, -45, -90, 24, 66, 75, 170, 802]

D [24, 66, 75, 170, 802, -2, -45, -90]

💡 Hint

Negative numbers are sorted by absolute value then reversed and negated to keep correct order.

The code separates negatives and positives, sorts them separately, then reverses and negates the negatives to maintain ascending order including negatives.

🔧 Debug

advanced

Identify the bug in Radix Sort implementation

What error or issue will occur when running this Radix Sort code?

DSA Javascript

function radixSortBug(arr) {
  const maxNum = Math.max(...arr);
  let digit = 1;
  while (maxNum / digit > 0) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let num of arr) {
      let digitNum = Math.floor((num / digit) % 10);
      buckets[digitNum].push(num);
    }
    arr = [].concat(...buckets);
    digit *= 10;
  }
  return arr;
}

const input = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSortBug(input));

A Infinite loop because the while condition never becomes false.

B SyntaxError due to missing parentheses in Math.floor.

C TypeError because buckets is not an array.

D Correct output: [2, 24, 45, 66, 75, 90, 170, 802]

💡 Hint

Check the while loop condition and how it changes each iteration.

The while loop condition uses maxNum / digit > 0 but digit is a number and maxNum / digit is a float; the loop never ends because the condition stays true when digit grows.

🚀 Application

expert

Radix Sort Stability and Output Order

Given the array of objects below, sorted by their 'value' property using Radix Sort, what will be the order of objects after sorting?

DSA Javascript

function radixSortObjects(arr) {
  const maxNum = Math.max(...arr.map(o => o.value));
  let digit = 1;
  while (Math.floor(maxNum / digit) > 0) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let obj of arr) {
      let digitNum = Math.floor((obj.value / digit) % 10);
      buckets[digitNum].push(obj);
    }
    arr = [].concat(...buckets);
    digit *= 10;
  }
  return arr;
}

const input = [
  {id: 'a', value: 21},
  {id: 'b', value: 12},
  {id: 'c', value: 21},
  {id: 'd', value: 10}
];

const sorted = radixSortObjects(input);
console.log(sorted.map(o => o.id));

A ['d', 'a', 'c', 'b']

B ['b', 'd', 'a', 'c']

C ['a', 'c', 'b', 'd']

D ['d', 'b', 'a', 'c']

💡 Hint

Radix Sort is stable, so objects with the same value keep their original relative order.

Radix Sort preserves the order of objects with equal keys. Both 'a' and 'c' have value 21, and 'a' appears before 'c' originally, so after sorting, 'a' stays before 'c'. The sorted order by value is 10, 12, 21, 21, so ids are ['d', 'b', 'a', 'c'].