Counting Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Counting Sort Algorithm

Find max value in input array

↓

Create count array of size max+1

↓

Count frequency of each element

↓

Modify count array to store cumulative counts

↓

Place elements into output array using count array

↓

Copy output array back to input array

↓

Done

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

Execution Sample

DSA Go

input := []int{4, 2, 2, 8, 3, 3, 1}
max := 8
count := make([]int, max+1)
for _, num := range input {
	count[num]++
}
for i := 1; i <= max; i++ {
	count[i] += count[i-1]
}
output := make([]int, len(input))
for i := len(input)-1; i >= 0; i-- {
	val := input[i]
	output[count[val]-1] = val
	count[val]--
}
copy(input, output)

This code sorts the input array by counting occurrences and placing elements in order.

Execution Table

Step	Operation	Input Array	Count Array	Output Array	Notes
1	Initial input	[4, 2, 2, 8, 3, 3, 1]	[0,0,0,0,0,0,0,0,0]	[_,_,_,_,_,_,_]	Start with empty count and output arrays
2	Count 4	[4, 2, 2, 8, 3, 3, 1]	[0,0,0,0,1,0,0,0,0]	[_,_,_,_,_,_,_]	Increment count[4]
3	Count 2	[4, 2, 2, 8, 3, 3, 1]	[0,0,2,0,1,0,0,0,0]	[_,_,_,_,_,_,_]	Increment count[2] twice
4	Count 8	[4, 2, 2, 8, 3, 3, 1]	[0,0,2,0,1,0,0,0,1]	[_,_,_,_,_,_,_]	Increment count[8]
5	Count 3	[4, 2, 2, 8, 3, 3, 1]	[0,0,2,2,1,0,0,0,1]	[_,_,_,_,_,_,_]	Increment count[3] twice
6	Count 1	[4, 2, 2, 8, 3, 3, 1]	[0,1,2,2,1,0,0,0,1]	[_,_,_,_,_,_,_]	Increment count[1]
7	Cumulative count step 1	[4, 2, 2, 8, 3, 3, 1]	[0,1,3,5,6,6,6,6,7]	[_,_,_,_,_,_,_]	Each count[i] += count[i-1]
8	Place 1	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,5,6,6,6,6,7]	[1,_,_,_,_,_,_]	Place 1 at output[count[1]-1=0], decrement count[1]
9	Place 3	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,4,6,6,6,6,7]	[1,_,_,_,3,_,_]	Place 3 at output[count[3]-1=4], decrement count[3]
10	Place 3	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,3,6,6,6,6,7]	[1,_,_,3,3,_,_]	Place second 3 at output[count[3]-1=3], decrement count[3]
11	Place 8	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,3,6,6,6,6,6]	[1,_,_,3,3,_,8]	Place 8 at output[count[8]-1=6], decrement count[8]
12	Place 2	[4, 2, 2, 8, 3, 3, 1]	[0,0,2,3,6,6,6,6,6]	[1,_,2,3,3,_,8]	Place 2 at output[count[2]-1=2], decrement count[2]
13	Place 2	[4, 2, 2, 8, 3, 3, 1]	[0,0,1,3,6,6,6,6,6]	[1,2,2,3,3,_,8]	Place second 2 at output[count[2]-1=1], decrement count[2]
14	Place 4	[4, 2, 2, 8, 3, 3, 1]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	Place 4 at output[count[4]-1=5], decrement count[4]
15	Copy output to input	[1,2,2,3,3,4,8]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	Sorted array copied back
16	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

💡 All elements placed in output and copied back; input array is sorted.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 15	Final
input	[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]	[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]

Key Moments - 3 Insights

Why do we create a count array of size max+1?

Because we need to count frequencies for every number from 0 up to the maximum value, so the array must have max+1 slots (see execution_table step 1).

Why do we modify the count array to cumulative counts?

Cumulative counts tell us the exact position where each element should go in the output array (see execution_table step 7).

Why do we place elements in output array from right to left?

Placing from right to left keeps the sort stable, preserving the order of equal elements (see execution_table steps 8-14).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the value of count[3]?

A 5

B 2

C 4

D 6

💡 Hint

Check the 'Count Array' column at step 7 in execution_table.

At which step does the output array first get the element '8' placed?

A Step 10

B Step 11

C Step 12

D Step 14

💡 Hint

Look at the 'Operation' and 'Output Array' columns in execution_table for when '8' appears.

If the input array had a maximum value of 10 instead of 8, how would the count array size change?

A It would stay the same size

B It would be size 8

C It would be size 11

D It would be size 10

💡 Hint

Recall count array size is max+1, see concept_flow first step.

Concept Snapshot

Counting Sort Algorithm:
- Find max value in input
- Create count array size max+1
- Count frequencies of each element
- Convert count to cumulative counts
- Place elements in output using count
- Copy output back to input
- Stable and efficient for small range integers

Full Transcript

Counting Sort works by first finding the maximum value in the input array. Then it creates a count array with size max+1 to hold frequencies of each number. Next, it counts how many times each number appears. After that, it changes the count array to cumulative counts, which tell where each number should be placed in the output array. Then it places each element from the input into the output array in order, using the count array to find the correct position. Finally, it copies the sorted output back to the input array. This method is stable and fast when the range of numbers is not too large.

Practice

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

easy

A. Swapping adjacent elements if they are in wrong order

B. Comparing each element with every other element

C. Counting the number of occurrences of each element to sort

D. Dividing the array into halves and sorting recursively

Solution

1. Step 1: Understand Counting Sort principle

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

2. Step 2: Use counts to place elements in order

   Using these counts, it places elements directly in sorted order without comparisons.

3. Final Answer:

   Counting the number of occurrences of each element to sort -> Option C

4. Quick Check:

   Counting occurrences = D [OK]

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

Common Mistakes:

• Thinking it compares elements like bubble sort
• Confusing with divide and conquer methods
• Assuming it swaps elements repeatedly

2. Which of the following is the correct way to declare the count array in Go for counting sort when input values range from 0 to 9?

easy

A. count := make([]int, 10)

B. count := make([]int, 9)

C. count := make([]int, 11)

D. count := make([]int, 0)

Solution

1. Step 1: Determine size of count array

   For values 0 to 9, we need 10 slots to count each number.

2. Step 2: Use make function with correct length

   Using make([]int, 10) creates an integer slice of length 10, perfect for counting 0-9.

3. Final Answer:

   count := make([]int, 10) -> Option A

4. Quick Check:

   Length 10 for 0-9 range = A [OK]

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

Common Mistakes:

• Using length 9 misses counting number 9
• Using length 0 creates empty slice
• Using length 11 wastes space unnecessarily

3. What will be the output of the following Go code snippet using counting sort logic?

arr := []int{4, 2, 2, 8, 3, 3, 1}
count := make([]int, 9)
for _, v := range arr {
    count[v]++
}
var sorted []int
for i, c := range count {
    for j := 0; j < c; j++ {
        sorted = append(sorted, i)
    }
}
fmt.Println(sorted)

medium

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

B. [4 2 2 8 3 3 1]

C. [1 2 3 4 8]

D. [1 2 2 3 3 4 8]

Solution

1. Step 1: Count occurrences of each number

   Count array after loop: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1, others 0.

2. Step 2: Build sorted slice using counts

   Append each number i count[i] times: 1 once, 2 twice, 3 twice, 4 once, 8 once.

3. Final Answer:

   [1 2 2 3 3 4 8] -> Option D

4. Quick Check:

   Sorted array = [1 2 2 3 3 4 8] [OK]

Hint: Count then expand counts in order to sort [OK]

Common Mistakes:

• Printing original array instead of sorted
• Including zero counts as elements
• Miscounting duplicates

4. Identify the bug in this Go code snippet implementing counting sort:

arr := []int{3, 1, 4, 1, 5}
count := make([]int, 6)
for _, v := range arr {
    count[v]++
}
var sorted []int
for i, c := range count {
    for j := 0; j <= c; j++ {
        sorted = append(sorted, i)
    }
}
fmt.Println(sorted)

medium

A. Inner loop uses <= instead of < causing extra elements

B. Count array size is too small for max value 5

C. Appending index instead of value

D. Missing initialization of sorted slice

Solution

1. Step 1: Check count array size

   Count array size 6 covers indices 0-5, correct for max value 5.

2. Step 2: Analyze inner loop condition

   Inner loop uses j <= c, which runs one extra time than needed, adding one extra element per non-zero count.

3. Final Answer:

   Inner loop uses <= instead of < causing extra elements -> Option A

4. Quick Check:

   Loop condition off by one = A [OK]

Hint: Use < not <= in loops counting occurrences [OK]

Common Mistakes:

• Ignoring off-by-one errors in loops
• Assuming count array size error causes runtime panic
• Confusing index and value in append

5. Given an array with negative and positive integers: arr := []int{-2, -1, 0, 1, 2}, how can you adapt counting sort to sort this array correctly?

hard

A. Use counting sort directly without changes

B. Shift all values by adding 2 to make them non-negative, then apply counting sort

C. Sort only positive numbers and append negatives at the end

D. Counting sort cannot be used with negative numbers

Solution

1. Step 1: Identify problem with negatives in counting sort

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

2. Step 2: Shift values to non-negative range

   Add the absolute value of the minimum (2) to all elements, making them 0 to 4, then apply counting sort.

3. Final Answer:

   Shift all values by adding 2 to make them non-negative, then apply counting sort -> Option B

4. Quick Check:

   Shift negatives to zero-based index = B [OK]

Hint: Shift negatives to zero or positive before counting [OK]

Common Mistakes:

• Trying to use negative indices directly
• Ignoring negative values in sorting
• Assuming counting sort works on all integers without adjustment