Counting Sort Algorithm in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the count array with zeros.

DSA Javascript

const count = new Array(max + 1).fill([1]);

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

A0

B1

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 causes incorrect counts.

Using null or undefined causes errors when incrementing.

Counting sort uses a count array initialized with zeros to store frequencies.

2fill in blank

medium

Complete the code to count the frequency of each element in the input array.

DSA Javascript

for (let i = 0; i < arr.length; i++) {
  count[arr[i]] [1];
}

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

A=

B--

C++

D+=

Attempts:

3 left

💡 Hint

Common Mistakes

Using -- decreases the count incorrectly.

Using = overwrites the count instead of incrementing.

We increment the count for each element found in the input array.

3fill in blank

hard

Fix the error in the code to compute the cumulative count correctly.

DSA Javascript

for (let i = 1; i <= max; i++) {
  count[i] = count[i] [1] count[i - 1];
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction causes wrong cumulative counts.

Using multiplication or division is incorrect here.

Cumulative count is the sum of current count and previous counts.

4fill in blank

hard

Fill both blanks to place elements in the output array in stable order.

DSA Javascript

for (let i = arr.length - 1; i >= 0; i--) {
  output[count[arr[i]] [1]] = arr[i];
  count[arr[i]] [2];
}

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

A- 1

B+ 1

C--

D++

Attempts:

3 left

💡 Hint

Common Mistakes

Not subtracting 1 causes index errors.

Incrementing count instead of decrementing breaks stability.

We place the element at index count[element] - 1 and then decrement the count.

5fill in blank

hard

Fill all three blanks to copy the sorted output back to the original array.

DSA Javascript

for (let i = 0; i < arr.length; ) {
  arr[[1]] = output[[2]];
  [3];
}

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

Ai

Ci++

D++i

Attempts:

3 left

💡 Hint

Common Mistakes

Using different indices causes wrong copying.

Forgetting to increment i causes infinite loop.

We copy each element from output to arr using index i and increment i.

Practice

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

easy

A. Swap adjacent elements if they are in wrong order repeatedly

B. Compare each element with every other element to sort

C. Count the occurrences of each element and use counts to place elements in order

D. Divide the array into halves and sort recursively

Solution

1. Step 1: Understand Counting Sort principle

   Counting sort counts how many times each value appears in the input array.

2. Step 2: Use counts to place elements

   Using these counts, it calculates positions to place each element in the sorted output.

3. Final Answer:

   Count the occurrences of each element and use counts to place elements in order -> Option C

4. Quick Check:

   Counting elements = Counting Sort [OK]

Hint: Counting sort counts elements, no comparisons needed [OK]

Common Mistakes:

• Thinking counting sort compares elements like bubble sort
• Confusing counting sort with divide and conquer methods
• Assuming counting sort works on all data types

2. Which of the following is the correct way to initialize the count array in Counting Sort for input array arr with maximum value maxVal in JavaScript?

easy

A. const count = new Array().fill(maxVal + 1);

B. const count = new Array(maxVal).fill(0);

C. const count = new Array(arr.length).fill(0);

D. const count = new Array(maxVal + 1).fill(0);

Solution

1. Step 1: Determine size of count array

   The count array must cover all values from 0 to maxVal, so size is maxVal + 1.

2. Step 2: Initialize count array with zeros

   Use new Array(maxVal + 1).fill(0) to create and fill with zeros.

3. Final Answer:

   const count = new Array(maxVal + 1).fill(0); -> Option D

4. Quick Check:

   Count array size = maxVal + 1 [OK]

Hint: Count array length = max value + 1 [OK]

Common Mistakes:

• Using maxVal instead of maxVal + 1 for array size
• Using input array length instead of maxVal
• Incorrectly filling array with maxVal + 1 instead of zeros

3. What will be the output of the following JavaScript code using Counting Sort?

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

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

medium

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

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

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

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

Solution

1. Step 1: Count occurrences of each number

   Count array after counting: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1.

2. Step 2: Build sorted array using counts

   Push each number count[i] times in ascending order: 1, 2, 2, 3, 3, 4, 8.

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option A

4. Quick Check:

   Sorted array matches counting sort output [OK]

Hint: Counting sort output is sorted array with duplicates in order [OK]

Common Mistakes:

• Returning original array instead of sorted
• Reversing order by mistake
• Missing duplicates in output

4. Identify the bug in this Counting Sort implementation and select the fix:

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

medium

A. Change count array size to maxVal + 1 and loop to i <= maxVal

B. Initialize count array with zeros using fill(1)

C. Use for loop from i = 1 to maxVal instead of 0

D. Remove the while loop and use if condition instead

Solution

1. Step 1: Check count array size and loop range

   Count array size is maxVal but should be maxVal + 1 to include maxVal index.

2. Step 2: Fix loop to include maxVal index

   Loop should run from 0 to maxVal inclusive (i <= maxVal) to cover all counts.

3. Final Answer:

   Change count array size to maxVal + 1 and loop to i <= maxVal -> Option A

4. Quick Check:

   Count array size and loop range must match maxVal + 1 [OK]

Hint: Count array size = maxVal + 1; loop to i <= maxVal [OK]

Common Mistakes:

• Using wrong count array size causing index errors
• Looping less than needed, missing maxVal counts
• Changing fill value incorrectly

5. Given an array arr = [5, 3, 0, 2, 3, 5, 1], how would you modify Counting Sort to sort only the elements between 1 and 4 inclusive, ignoring others?

hard

A. Use counting sort on full range but skip pushing elements outside 1 to 4

B. Count only elements between 1 and 4, then output sorted elements in that range

C. Sort entire array normally and then remove elements outside 1 to 4

D. Filter array first, then apply counting sort on filtered array

Solution

1. Step 1: Count only elements in range 1 to 4

   Ignore elements outside 1 to 4 while counting to focus sorting on this range.

2. Step 2: Output sorted elements only in that range

   Build sorted array using counts only for values 1 to 4, ignoring others.

3. Final Answer:

   Count only elements between 1 and 4, then output sorted elements in that range -> Option B

4. Quick Check:

   Counting and output limited to range [1,4] [OK]

Hint: Count and output only target range elements [OK]

Common Mistakes:

• Sorting full array then filtering, wasting effort
• Counting full range but skipping output incorrectly
• Filtering after sorting instead of before