Radix Sort Algorithm in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the digit at a specific place value.

DSA Javascript

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / [1]) % 10;
}

Drag options to blanks, or click blank then click option'

A10 ** place

Bplace * 10

Cplace + 10

D10 * place

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of exponentiation for place value.

Not using Math.floor to remove decimals.

The digit at a given place is found by dividing the number by 10 raised to that place, then taking the remainder when divided by 10.

2fill in blank

medium

Complete the code to count the number of digits in a number.

DSA Javascript

function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + [1];
}

Drag options to blanks, or click blank then click option'

A0

B1

C10

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting to add 1 after log10.

Not handling zero correctly.

Adding 1 after floor of log base 10 gives the total digits count.

3fill in blank

hard

Fix the error in the code to find the maximum number of digits in an array.

DSA Javascript

function mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, [1](nums[i]));
  }
  return maxDigits;
}

Drag options to blanks, or click blank then click option'

AMath.abs

BgetDigit

CMath.log10

DdigitCount

Attempts:

3 left

💡 Hint

Common Mistakes

Using getDigit which returns a single digit, not count.

Using Math.log10 directly without floor or handling zero.

We use digitCount to find how many digits each number has and track the maximum.

4fill in blank

hard

Fill both blanks to correctly place numbers into buckets by digit and flatten the array.

DSA Javascript

for (let k = 0; k < maxDigitCount; k++) {
  let buckets = Array.from({ length: 10 }, () => []);
  for (let i = 0; i < nums.length; i++) {
    let digit = [1](nums[i], k);
    buckets[digit].[2](nums[i]);
  }
  nums = [].concat(...buckets);
}

Drag options to blanks, or click blank then click option'

AgetDigit

Bpush

Cpop

Dshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop or shift which remove elements instead of adding.

Using digitCount instead of getDigit here.

getDigit gets the digit at place k; push adds the number to the correct bucket.

5fill in blank

hard

Fill all three blanks to complete the radix sort function.

DSA Javascript

function radixSort(nums) {
  let maxDigitCount = [1](nums);
  for (let k = 0; k < maxDigitCount; k++) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < nums.length; i++) {
      let digit = [2](nums[i], k);
      buckets[digit].push(nums[i]);
    }
    nums = [].concat(...buckets);
  }
  return nums;
}

// Helper functions
function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

function mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / (10 ** place)) % 10;
}

Drag options to blanks, or click blank then click option'

AmostDigits

BgetDigit

CdigitCount

DMath.max

Attempts:

3 left

💡 Hint

Common Mistakes

Using digitCount instead of mostDigits for maxDigitCount.

Using digitCount inside the loop instead of getDigit.

mostDigits finds max digits in array, getDigit gets digit at place, digitCount counts digits.

Practice

1. What is the main idea behind the Radix Sort Algorithm?

easy

A. Sort numbers by swapping adjacent elements repeatedly

B. Sort numbers by comparing each pair directly

C. Sort numbers by dividing them into two halves recursively

D. Sort numbers digit by digit starting from the least significant digit

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing each digit separately, starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, Radix Sort groups numbers by digits without direct comparisons between whole numbers.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option D

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Radix Sort processes digits from right to left [OK]

Common Mistakes:

• Thinking Radix Sort compares whole numbers directly
• Confusing Radix Sort with quicksort or mergesort
• Assuming it sorts from most significant digit first

2. Which of the following is the correct way to initialize a bucket array for Radix Sort in JavaScript?

easy

A. const buckets = [].map(() => []);

B. const buckets = new Array(10).fill([]);

C. const buckets = Array.from({ length: 10 }, () => []);

D. const buckets = Array(10).fill(null);

Solution

1. Step 1: Understand bucket initialization

   We need 10 separate arrays (buckets) for digits 0-9. Using Array.from with a function creates independent arrays.

2. Step 2: Why other options fail

   const buckets = new Array(10).fill([]); fills with the same array reference, causing all buckets to share one array. const buckets = [].map(() => []); fails because map on empty array does nothing. const buckets = Array(10).fill(null); fills with null, not arrays.

3. Final Answer:

   const buckets = Array.from({ length: 10 }, () => []); -> Option C

4. Quick Check:

   Use Array.from with function for separate buckets [OK]

Hint: Use Array.from with arrow function for unique buckets [OK]

Common Mistakes:

• Using fill([]) creates shared references
• Using map on uninitialized array returns empty
• Filling buckets with null instead of arrays

3. What will be the output of the following JavaScript code snippet using Radix Sort on the array [170, 45, 75, 90, 802, 24, 2, 66]?

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

function radixSort(arr) {
  let maxDigit = Math.floor(Math.log10(Math.max(...arr))) + 1;
  for (let k = 0; k < maxDigit; k++) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let num of arr) {
      buckets[getDigit(num, k)].push(num);
    }
    arr = [].concat(...buckets);
  }
  return arr;
}

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

medium

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

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

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

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

Solution

1. Step 1: Understand digit extraction and sorting

   The code sorts numbers by each digit from least significant (units) to most significant. After each pass, numbers are grouped by that digit.

2. Step 2: Trace sorting passes

   After sorting by units digit, then tens, then hundreds, the array becomes fully sorted ascending: [2, 24, 45, 66, 75, 90, 170, 802].

3. Final Answer:

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

4. Quick Check:

   Radix Sort output = Sorted ascending array [OK]

Hint: Radix Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing original array with sorted output
• Misunderstanding digit extraction order
• Assuming sorting is descending

4. Identify the bug in this Radix Sort snippet and choose the correct fix:

function radixSort(arr) {
  let maxDigit = Math.floor(Math.log10(Math.max(...arr))) + 1;
  for (let k = 0; k <= maxDigit; k++) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let num of arr) {
      buckets[Math.floor(num / Math.pow(10, k)) % 10].push(num);
    }
    arr = [].concat(...buckets);
  }
  return arr;
}

medium

A. Change loop condition to k < maxDigit instead of <= maxDigit

B. Initialize buckets with new Array(10).fill([])

C. Use Math.ceil instead of Math.floor for maxDigit

D. Remove Math.abs from digit calculation

Solution

1. Step 1: Analyze loop range for digit passes

   The loop runs from 0 to maxDigit inclusive, causing one extra pass beyond needed digits.

2. Step 2: Fix loop condition

   Changing k <= maxDigit to k < maxDigit ensures exactly maxDigit passes, avoiding unnecessary iteration.

3. Final Answer:

   Change loop condition to k < maxDigit instead of <= maxDigit -> Option A

4. Quick Check:

   Loop runs maxDigit times, not maxDigit+1 [OK]

Hint: Loop digits from 0 to less than maxDigit [OK]

Common Mistakes:

• Using <= causes extra unnecessary pass
• Initializing buckets incorrectly with shared arrays
• Changing floor to ceil breaks digit count

5. You want to use Radix Sort to sort an array containing both positive and negative integers, like [170, -45, 75, -90, 802, 24, -2, 66]. Which approach correctly adapts Radix Sort for this case?

hard

A. Separate negative and positive numbers, sort positives with Radix Sort, sort negatives by absolute value then reverse, then combine

B. Apply Radix Sort directly on all numbers including negatives without changes

C. Convert all numbers to strings and sort lexicographically

D. Use Radix Sort only on positive numbers and ignore negatives

Solution

1. Step 1: Understand Radix Sort limitation

   Radix Sort works only on non-negative integers because it sorts digits from least significant to most significant.

2. Step 2: Adapt for negatives

   Separate negatives and positives. Sort positives normally. For negatives, sort their absolute values, then reverse the result to get correct order. Finally, combine negatives (in reversed order) before positives.

3. Final Answer:

   Separate negative and positive numbers, sort positives with Radix Sort, sort negatives by absolute value then reverse, then combine -> Option A

4. Quick Check:

   Separate negatives and positives, sort separately [OK]

Hint: Sort negatives by absolute then reverse, positives normally [OK]

Common Mistakes:

• Trying to sort negatives directly with Radix Sort
• Ignoring negative numbers in sorting
• Sorting numbers as strings causing wrong order