Counting Sort Algorithm in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a small array

What is the output of the following counting sort implementation on the array [4, 2, 2, 8, 3, 3, 1]?

DSA Javascript

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (const num of arr) {
    count[num]++;
  }
  let sortedIndex = 0;
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      arr[sortedIndex++] = i;
      count[i]--;
    }
  }
  return arr;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));

A [1, 2, 3, 4, 8]

B [1, 2, 2, 3, 3, 4, 8]

C [8, 4, 3, 3, 2, 2, 1]

D [1, 1, 2, 2, 3, 3, 4, 8]

💡 Hint

Counting sort counts how many times each number appears and then rebuilds the array in order.

The counting sort counts the frequency of each number and then places them back in sorted order. The input array has one 1, two 2s, two 3s, one 4, and one 8. So the sorted array is [1, 2, 2, 3, 3, 4, 8].

🧠 Conceptual

intermediate

Counting Sort Stability Property

Which statement correctly describes the stability of counting sort?

A Counting sort is unstable because it uses a hash map internally.

B Counting sort is unstable because it rearranges equal elements randomly.

C Counting sort is stable only if the input array is already sorted.

D Counting sort is stable because it preserves the relative order of equal elements.

💡 Hint

Think about whether equal numbers keep their original order after sorting.

Counting sort is stable because it places elements in the output array in the order they appear in the input, preserving the relative order of equal elements.

🔧 Debug

advanced

Identify the error in this counting sort code

What error will this code produce when run on the array [3, 1, 2]?

DSA Javascript

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max).fill(0);
  for (const num of arr) {
    count[num]++;
  }
  let sortedIndex = 0;
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      arr[sortedIndex++] = i;
      count[i]--;
    }
  }
  return arr;
}

console.log(countingSort([3, 1, 2]));

A TypeError: Cannot read property '3' of undefined

B RangeError: Maximum call stack size exceeded

C Output: [1, 2, 3]

D ReferenceError: max is not defined

💡 Hint

Check how the count array is created and accessed.

The count array is created with length max (3), so indices 0,1,2 exist. But the code tries to access count[3] which is undefined, causing a TypeError when incrementing count[3].

🚀 Application

advanced

Counting Sort with Negative Numbers

Given the array [-5, -10, 0, -3, 8, 5, -1, 10], which approach correctly adapts counting sort to handle negative numbers?

A Convert all numbers to strings and sort lexicographically.

B Ignore negative numbers and sort only positive numbers using counting sort.

C Shift all numbers by adding the absolute value of the minimum number before sorting, then shift back after sorting.

D Use counting sort directly without changes; it handles negatives automatically.

💡 Hint

Counting sort uses array indices as counts, so negative indices are invalid.

Counting sort cannot use negative indices. Shifting all numbers by adding the absolute value of the minimum number makes all numbers non-negative, allowing counting sort to work. After sorting, shift back to original values.

❓ Predict Output

expert

Output of Counting Sort with Frequency Array

What is the output of this code snippet?

DSA Javascript

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (const num of arr) {
    count[num]++;
  }
  const result = [];
  for (let i = 0; i < count.length; i++) {
    for (let j = 0; j < count[i]; j++) {
      result.push(i);
    }
  }
  return result;
}

const input = [2, 5, 3, 0, 2, 3, 0, 3];
console.log(countingSort(input));

A [0, 0, 2, 2, 3, 3, 3, 5]

B [0, 0, 2, 3, 3, 3, 5]

C [0, 0, 2, 3, 3, 5]

D [0, 0, 2, 3, 5]

💡 Hint

Count how many times each number appears and list them in order.

The input has two 0s, two 2s, three 3s, and one 5. So the sorted output is [0, 0, 2, 2, 3, 3, 3, 5].