Counting Sort Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a Small Array

What is the output of the following counting sort implementation on the array [4, 2, 2, 8, 3, 3, 1]?

DSA Python

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i, c in enumerate(count):
        sorted_arr.extend([i] * c)
    return sorted_arr

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

A [1, 2, 2, 3, 3, 4, 8]

B [1, 2, 3, 4, 8]

C [8, 4, 3, 3, 2, 2, 1]

D [1, 1, 2, 2, 3, 3, 4, 8]

💡 Hint

Counting sort counts how many times each number appears and then reconstructs the sorted list.

The counting sort counts the frequency of each number and then outputs them in order. The input array has one 1, two 2s, two 3s, one 4, and one 8, so the sorted output is [1, 2, 2, 3, 3, 4, 8].

🧠 Conceptual

intermediate

Counting Sort Characteristics

Which of the following statements about counting sort is TRUE?

A Counting sort is a comparison-based sorting algorithm.

B Counting sort can sort negative numbers without any modification.

C Counting sort always requires extra space proportional to the number of elements squared.

D Counting sort works well only when the range of input values is not significantly larger than the number of elements.

💡 Hint

Think about how counting sort uses an array indexed by input values.

Counting sort uses an array sized by the range of input values. If the range is much larger than the number of elements, it becomes inefficient. It is not comparison-based and does not handle negative numbers without modification.

🔧 Debug

advanced

Identify the Bug in Counting Sort Implementation

What error will this counting sort code produce when run on the array [3, 1, 2]?

DSA Python

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * max_val
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i, c in enumerate(count):
        sorted_arr.extend([i] * c)
    return sorted_arr

print(counting_sort([3, 1, 2]))

A [1, 2, 3]

B IndexError: list index out of range

C TypeError: unsupported operand type(s)

D ValueError: max() arg is an empty sequence

💡 Hint

Check how the count array size relates to max_val and indexing.

The count array is created with size max_val, but since list indices start at 0, the index max_val is out of range. For example, max_val=3 but count has length 3 (indices 0,1,2). Accessing count[3] causes IndexError.

❓ Predict Output

advanced

Counting Sort Output with Duplicate and Zero

What is the output of this counting sort code on the array [0, 5, 3, 0, 2, 5, 1]?

DSA Python

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i, c in enumerate(count):
        sorted_arr.extend([i] * c)
    return sorted_arr

print(counting_sort([0, 5, 3, 0, 2, 5, 1]))

A [0, 0, 1, 2, 3, 5, 5]

B [0, 1, 2, 3, 5]

C [5, 5, 3, 2, 1, 0, 0]

D [0, 0, 1, 2, 3, 5]

💡 Hint

Remember counting sort includes all duplicates and zeros in the output.

The input has two zeros, one 1, one 2, one 3, and two 5s. Counting sort outputs all in sorted order including duplicates.

🧠 Conceptual

expert

Counting Sort Stability and Use Cases

Which statement about counting sort is CORRECT?

A Counting sort is unstable and requires comparison operations between elements.

B Counting sort is unstable and cannot be used for sorting objects with keys.

C Counting sort is stable and can be used to sort objects by keys when keys are integers in a small range.

D Counting sort is stable but only works for floating-point numbers.

💡 Hint

Think about whether counting sort preserves the order of equal elements and what types of keys it handles.

Counting sort is stable, meaning it preserves the order of equal elements. It works well for sorting objects by integer keys in a small range without comparisons.

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 to sort

C. Dividing the list into halves and sorting recursively

D. Counting the occurrences of each element and using that to place elements in order

Solution

1. Step 1: Understand Counting Sort principle

   Counting Sort counts how many times each value appears in the list.

2. Step 2: Use counts to place elements

   It then uses these counts to place elements directly in the sorted order without comparisons.

3. Final Answer:

   Counting the occurrences of each element and using that to place elements in order -> Option D

4. Quick Check:

   Counting occurrences = A [OK]

Hint: Counting Sort uses counts, not comparisons, to sort [OK]

Common Mistakes:

• Thinking Counting Sort compares elements
• Confusing Counting Sort with comparison-based sorts
• Assuming Counting Sort works on all data types

2. Which of the following is the correct way to initialize the count array for Counting Sort in Python for input values ranging from 0 to 5?

easy

A. count = [0] * 6

B. count = [0] * 5

C. count = [null] * 6

D. count = []

Solution

1. Step 1: Determine count array size

   For values 0 to 5 inclusive, we need 6 slots (0,1,2,3,4,5).

2. Step 2: Initialize count array with zeros

   Using [0] * 6 creates a list of six zeros to count occurrences.

3. Final Answer:

   count = [0] * 6 -> Option A

4. Quick Check:

   Length 6 with zeros = D [OK]

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

Common Mistakes:

• Using wrong size for count array
• Initializing with null instead of 0
• Leaving count array empty

3. What will be the output of the following Python code using Counting Sort on the list [4, 2, 2, 8, 3, 3, 1]?

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

medium

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

B. [8, 4, 3, 3, 2, 2, 1]

C. [1, 2, 3, 4, 8]

D. [0, 1, 2, 2, 3, 3, 4, 8]

Solution

1. Step 1: Count occurrences of each number

   Count array for max_val=8: counts for 1=1, 2=2, 3=2, 4=1, 8=1, others=0.

2. Step 2: Build sorted list using counts

   Extend sorted_arr with each number repeated by its count: [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option A

4. Quick Check:

   Sorted list matches counting sort output = B [OK]

Hint: Counting Sort output is sorted list with duplicates in order [OK]

Common Mistakes:

• Forgetting to repeat elements by their count
• Returning unsorted or reversed list
• Including zeros for missing elements

4. The following code attempts to implement Counting Sort but has a bug. What is the error?

def counting_sort_bug(arr):
    max_val = max(arr)
    count = [0] * max_val
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

print(counting_sort_bug([3, 1, 2, 3]))

medium

A. Count array initialized with zeros incorrectly

B. Loop to build sorted_arr uses wrong range

C. Count array size is too small, missing last element count

D. Function does not return anything

Solution

1. Step 1: Check count array size

   Count array size is max_val, but should be max_val + 1 to include max element index.

2. Step 2: Understand impact on counting

   Missing last index causes error when counting max element (3), leading to IndexError or wrong counts.

3. Final Answer:

   Count array size is too small, missing last element count -> Option C

4. Quick Check:

   Count array size = max_val + 1 [OK]

Hint: Count array size must be max value + 1 [OK]

Common Mistakes:

• Using max_val instead of max_val + 1 for count array size
• Ignoring IndexError from out-of-range access
• Not initializing count array properly

5. You have a list of exam scores ranging from 0 to 100, but some scores are missing. How can you modify Counting Sort to efficiently sort this list and also find how many students scored exactly 75?

hard

A. Use a comparison sort and count 75s during sorting

B. Use Counting Sort normally, then check count[75] for number of students scoring 75

C. Sort with Counting Sort and then scan sorted list to count 75s

D. Use Counting Sort but ignore counts for missing scores

Solution

1. Step 1: Apply Counting Sort on scores 0-100

   Create count array of size 101, count occurrences of each score.

2. Step 2: Use count array to find number of 75 scores

   Count at index 75 directly gives number of students scoring 75 without scanning sorted list.

3. Final Answer:

   Use Counting Sort normally, then check count[75] for number of students scoring 75 -> Option B

4. Quick Check:

   Counting array index = score count, access directly [OK]

Hint: Counting array index = score count, access directly [OK]

Common Mistakes:

• Scanning sorted list instead of using count array
• Ignoring missing scores in count array
• Using slower comparison sorts unnecessarily