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.