Counting Sort Algorithm in DSA Go - Build from Scratch

Counting Sort Algorithm

📖 Scenario: You work in a warehouse where you need to sort boxes by their weight quickly. Each box's weight is a small whole number. You want to organize them from lightest to heaviest using a fast method.

🎯 Goal: Build a program that sorts a list of box weights using the counting sort algorithm. This method counts how many boxes have each weight and then arranges them in order.

📋 What You'll Learn

Create a slice called weights with exact values: 4, 2, 2, 8, 3, 3, 1

Create a variable called maxWeight to store the highest weight in weights

Implement counting sort logic using a count slice to store frequencies

Print the sorted slice of weights

💡 Why This Matters

🌍 Real World

Counting sort is useful in warehouses or factories where items have small integer weights or categories and need fast sorting.

💼 Career

Understanding counting sort helps in roles like software development and data processing where efficient sorting of limited-range data is required.

1

Create the initial weights slice

Create a slice called weights with these exact values: 4, 2, 2, 8, 3, 3, 1.

DSA Go

# Create the weights slice with the given values
# Your code here

Hint

Use weights := []int{4, 2, 2, 8, 3, 3, 1} to create the slice.

2

Find the maximum weight

Create a variable called maxWeight and set it to the highest value in the weights slice by checking each element.

DSA Go

package main

func main() {
    weights := []int{4, 2, 2, 8, 3, 3, 1}
    // Find the maximum weight in weights
    // Your code here
}

Hint

Start with the first weight as maxWeight. Then check each weight and update maxWeight if you find a bigger one.

3

Implement counting sort logic

Create a slice called count with length maxWeight + 1 to store counts. Then, use a for loop with variables _, w to count how many times each weight appears in weights. Next, create a slice called sorted to store the sorted weights. Use a for loop with variable weight from 0 to maxWeight to append each weight to sorted as many times as it appears in count.

DSA Go

package main

func main() {
    weights := []int{4, 2, 2, 8, 3, 3, 1}
    maxWeight := weights[0]
    for _, w := range weights {
        if w > maxWeight {
            maxWeight = w
        }
    }
    // Create count slice and count frequencies
    // Create sorted slice and fill it using count
    // Your code here
}

Hint

Use make([]int, maxWeight+1) to create the count slice. Count each weight, then build the sorted slice by repeating weights according to their counts.

4

Print the sorted weights

Use fmt.Println(sorted) to print the sorted slice of weights.

DSA Go

package main

import "fmt"

func main() {
    weights := []int{4, 2, 2, 8, 3, 3, 1}
    maxWeight := weights[0]
    for _, w := range weights {
        if w > maxWeight {
            maxWeight = w
        }
    }

    count := make([]int, maxWeight+1)
    for _, w := range weights {
        count[w]++
    }

    sorted := []int{}
    for weight := 0; weight <= maxWeight; weight++ {
        for i := 0; i < count[weight]; i++ {
            sorted = append(sorted, weight)
        }
    }
    // Print the sorted slice
    // Your code here
}

Hint

Use fmt.Println(sorted) to show the sorted weights.

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