Counting Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a small array

What is the output of the following Go code that implements counting sort on the array [4, 2, 2, 8, 3, 3, 1]?

DSA Go

package main
import "fmt"
func countingSort(arr []int) []int {
    max := arr[0]
    for _, v := range arr {
        if v > max {
            max = v
        }
    }
    count := make([]int, max+1)
    for _, v := range arr {
        count[v]++
    }
    index := 0
    for i, c := range count {
        for c > 0 {
            arr[index] = i
            index++
            c--
        }
    }
    return arr
}
func main() {
    arr := []int{4, 2, 2, 8, 3, 3, 1}
    sorted := countingSort(arr)
    fmt.Println(sorted)
}

A [1 2 3 3 4 8 8]

B [4 2 2 8 3 3 1]

C [8 4 3 3 2 2 1]

D [1 2 2 3 3 4 8]

💡 Hint

Counting sort counts how many times each number appears and then rebuilds the array in order.

The counting sort algorithm counts the frequency of each number and then places them back in sorted order. The output is the sorted array [1 2 2 3 3 4 8].

🧠 Conceptual

intermediate

Counting Sort Stability Property

Which statement correctly describes the stability property of counting sort?

A Counting sort is stable only if the input array is already sorted.

B Counting sort is unstable because it rearranges equal elements randomly.

C Counting sort is stable because it preserves the relative order of equal elements.

D Counting sort is unstable because it uses a hash map internally.

💡 Hint

Stability means equal elements keep their original order after sorting.

Counting sort is stable because it places elements in the output array in the order they appear in the input, preserving relative order of duplicates.

🔧 Debug

advanced

Identify the bug in this counting sort implementation

What error will the following Go code produce when run, and why? func countingSort(arr []int) []int { max := 0 for _, v := range arr { if v > max { max = v } } count := make([]int, max) for _, v := range arr { count[v]++ } index := 0 for i, c := range count { for c > 0 { arr[index] = i index++ c-- } } return arr }

A Runtime panic: nil pointer dereference

B Runtime panic: index out of range because count slice size is max instead of max+1

C Compilation error due to missing import statement

D No error, outputs sorted array correctly

💡 Hint

Check how the count slice size relates to the max value in the array.

The count slice is created with length max, but since array indices go from 0 to max, it should be max+1. Accessing count[max] causes index out of range panic.

🚀 Application

advanced

Counting Sort Usage Scenario

Which scenario is best suited for using counting sort instead of comparison-based sorting algorithms?

A Sorting a large list of integers where the range of values is small compared to the list size.

B Sorting a list of integers where the range is very large compared to the list size.

C Sorting a list of strings alphabetically.

D Sorting a list of floating-point numbers with many decimal places.

💡 Hint

Counting sort works best when the range of input values is not too large.

Counting sort is efficient when the range of input values is small relative to the number of elements, allowing linear time sorting.

❓ Predict Output

expert

Output of Counting Sort with Negative Numbers

What will happen if you run the following Go code that tries to apply counting sort on an array containing negative numbers? arr := []int{3, -1, 2, -1, 0} sorted := countingSort(arr) fmt.Println(sorted) Assume countingSort is the standard implementation that uses the maximum value to create the count array size.

A Runtime panic: index out of range due to negative index access in count array

B [ -1 -1 0 2 3 ]

C [ 0 2 3 -1 -1 ]

D Compilation error due to negative numbers

💡 Hint

Counting sort uses array indices for counts, which cannot be negative.

Counting sort does not handle negative numbers because it uses array indices to count occurrences. Negative numbers cause invalid negative indices, leading to runtime panic.