Counting Sort Algorithm in DSA Go

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by counting how many balls of each color you have, then lining them up color by color based on those counts.

Input array: [4, 2, 2, 8, 3, 3, 1]
Count array: [0, 1, 2, 2, 1, 0, 0, 0, 1]
Sorted output: [1, 2, 2, 3, 3, 4, 8]

Dry Run Walkthrough

Input: array: [4, 2, 2, 8, 3, 3, 1]

Goal: Sort the array in ascending order using counting sort

Step 1: Find the maximum value to know count array size

Input: [4, 2, 2, 8, 3, 3, 1]
Max value: 8

Why: We need to know how big the count array should be to cover all numbers

Step 2: Create count array of size max+1 and initialize with zeros

Count array: [0, 0, 0, 0, 0, 0, 0, 0, 0]

Why: Count array holds how many times each number appears

Step 3: Count each number's frequency in input

Count array after counting: [0, 1, 2, 2, 1, 0, 0, 0, 1]

Why: Counting frequency helps us know how many times to place each number

Step 4: Modify count array to hold cumulative counts

Cumulative count array: [0, 1, 3, 5, 6, 6, 6, 6, 7]

Why: Cumulative counts tell the position of each number in the sorted output

Step 5: Place each element from input into output array using count array

Output array after placing: [1, 2, 2, 3, 3, 4, 8]

Why: Using counts to place elements ensures sorted order without comparisons

Result:

Sorted array: [1, 2, 2, 3, 3, 4, 8]

Annotated Code

DSA Go

package main

import "fmt"

func countingSort(arr []int) []int {
	if len(arr) == 0 {
		return arr
	}

	// Find max value to size count array
	max := arr[0]
	for _, val := range arr {
		if val > max {
			max = val
		}
	}

	// Create count array
	count := make([]int, max+1)

	// Count frequency of each number
	for _, val := range arr {
		count[val]++
	}

	// Modify count array to cumulative counts
	for i := 1; i <= max; i++ {
		count[i] += count[i-1]
	}

	// Create output array
	output := make([]int, len(arr))

	// Place elements in output using count array
	for i := len(arr) - 1; i >= 0; i-- {
		val := arr[i]
		count[val]--
		output[count[val]] = val
	}

	return output
}

func main() {
	arr := []int{4, 2, 2, 8, 3, 3, 1}
	sorted := countingSort(arr)
	for i, val := range sorted {
		if i == len(sorted)-1 {
			fmt.Printf("%d\n", val)
		} else {
			fmt.Printf("%d, ", val)
		}
	}
}

for _, val := range arr { if val > max { max = val } }

Find maximum value to size count array

for _, val := range arr { count[val]++ }

Count frequency of each number

for i := 1; i <= max; i++ { count[i] += count[i-1] }

Convert counts to cumulative counts for positions

for i := len(arr) - 1; i >= 0; i-- { val := arr[i]; count[val]--; output[count[val]] = val }

Place elements in output array in sorted order using counts

Output

1, 2, 2, 3, 3, 4, 8

Complexity Analysis

Time: O(n + k) because we count frequencies in O(n) and process count array of size k (max value)

Space: O(n + k) because we use output array of size n and count array of size k

vs Alternative: Counting sort is faster than comparison sorts (O(n log n)) when k (max value) is not much larger than n

Edge Cases

empty array

returns empty array immediately without error

DSA Go

if len(arr) == 0 { return arr }

array with one element

returns the same single-element array

DSA Go

function handles normally without special case

array with all elements the same

count array counts one value, output array is same as input

DSA Go

count[val]++ counts frequency correctly

When to Use This Pattern

When you need to sort integers with a known small range quickly and without comparisons, reach for counting sort because it uses counting and positions instead of comparing elements.

Common Mistakes

Mistake: Not converting count array to cumulative counts before placing elements
Fix: Add loop to convert counts to cumulative counts to know correct positions

Mistake: Placing elements in output array from start to end, causing unstable sort
Fix: Place elements from end to start to maintain stability

Summary

Counting sort sorts integers by counting their occurrences and placing them using cumulative counts.

Use it when sorting integers with a limited range efficiently and stably.

The key insight is using counts to find exact positions without comparing elements.

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