Counting Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Counting Sort Algorithm

Find max value in array

↓

Create count array of size max+1

↓

Initialize count array with zeros

↓

Count each element's frequency

↓

Modify count array to store positions

↓

Build output array using count positions

↓

Copy output array back to original

↓

Sorted array ready

Counting Sort counts how many times each number appears, then uses that to place numbers in order.

Execution Sample

DSA Javascript

const arr = [4,2,2,8,3,3,1];
const max = 8;
const count = new Array(max+1).fill(0);
// Count frequencies
for (let num of arr) count[num]++;
// Modify count
for (let i=1; i<=max; i++) count[i]+=count[i-1];
// Build output
const output = new Array(arr.length);
for (let i=arr.length-1; i>=0; i--) {
  output[--count[arr[i]]] = arr[i];
}
// Copy output to original array
for(let i=0; i<arr.length; i++) {
  arr[i] = output[i];
}

This code sorts the array using counting sort by counting frequencies and placing elements in order.

Execution Table

Step	Operation	Array State	Count Array State	Output Array State	Pointer/Index Changes	Visual State
1	Initial array	[4, 2, 2, 8, 3, 3, 1]	[0,0,0,0,0,0,0,0,0]	[]	count initialized to zeros	arr: 4,2,2,8,3,3,1; count: all zeros; output: empty
2	Count frequencies	[4, 2, 2, 8, 3, 3, 1]	[0,1,2,2,1,0,0,0,1]	[]	count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1	count updated with frequencies of each number
3	Modify count to positions	[4, 2, 2, 8, 3, 3, 1]	[0,1,3,5,6,6,6,6,7]	[]	count cumulative sums	count now shows positions for each number
4	Build output from right to left	[4, 2, 2, 8, 3, 3, 1]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	i moves from 6 to 0; count updated after placing each element	output filled in sorted order; count decremented for each placement
5	Copy output to original	[1, 2, 2, 3, 3, 4, 8]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	arr overwritten with output	arr is now sorted
6	End	[1, 2, 2, 3, 3, 4, 8]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	Sorting complete	Final sorted array

💡 All elements placed in output; original array overwritten with sorted values

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
arr	[4,2,2,8,3,3,1]	[4,2,2,8,3,3,1]	[4,2,2,8,3,3,1]	[4,2,2,8,3,3,1]	[1,2,2,3,3,4,8]
count	[0,0,0,0,0,0,0,0,0]	[0,1,2,2,1,0,0,0,1]	[0,1,3,5,6,6,6,6,7]	[0,0,1,3,5,6,6,6,6]	[0,0,1,3,5,6,6,6,6]
output	[]	[]	[]	[1,2,2,3,3,4,8]	[1,2,2,3,3,4,8]
i	N/A	N/A	N/A	6 to 0	N/A

Key Moments - 3 Insights

Why do we modify the count array to store positions instead of just frequencies?

Modifying count to cumulative sums lets us know the exact position where each number should go in the output. See step 3 in execution_table where count changes from frequencies to positions.

Why do we build the output array from right to left?

Building from right to left keeps the sort stable by placing duplicates in correct order. Step 4 shows i moving from end to start, updating output and count accordingly.

What happens if the input array contains numbers outside the range of count array?

Counting sort requires knowing max value to size count array. If numbers exceed max, it causes errors or wrong results. Step 1 finds max to prevent this.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does the count array represent?

A Frequencies of each number

B Positions where each number should be placed

C Sorted output array

D Original input array

💡 Hint

Refer to the 'Count Array State' column at step 3 showing cumulative sums

At which step does the output array get fully filled with sorted elements?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check 'Output Array State' column; step 4 shows output filled

If the input array had a number 9, what would need to change in the code?

A Increase max to at least 9 and size count array accordingly

B Decrease max to 8

C No change needed

D Remove number 9 from input

💡 Hint

See step 1 where max is found to size count array

Concept Snapshot

Counting Sort Algorithm:
- Find max value in array
- Create count array sized max+1, initialize zeros
- Count frequencies of each element
- Modify count to cumulative sums (positions)
- Build output array from right to left using count
- Copy output back to original array
- Stable and efficient for small range integers

Full Transcript

Counting Sort works by counting how many times each number appears in the input array. First, it finds the maximum number to know how big the count array should be. Then it creates a count array filled with zeros. Next, it counts the frequency of each number in the input and stores it in the count array. After that, it modifies the count array to hold cumulative sums, which represent the positions where each number should be placed in the output array. The algorithm then builds the output array by placing elements from the input array into their correct positions, moving from right to left to keep the sort stable. Finally, it copies the sorted output back into the original array. This method is very efficient for sorting integers within a small range.

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