Counting Sort Algorithm in DSA Python - Execution Trace

Concept Flow - Counting Sort Algorithm

Find max value in input array

↓

Create count array of size max+1

↓

Initialize count array with zeros

↓

Count frequency of each element

↓

Modify count array to store cumulative counts

↓

Build output array by placing elements at correct positions

↓

Copy output array back to input array

↓

Sorting complete

Counting Sort counts how many times each number appears, then uses these counts to place numbers in order.

Execution Sample

DSA Python

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    for i in range(1, len(count)):
        count[i] += count[i-1]
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    for i in range(len(arr)):
        arr[i] = output[i]

This code sorts an array of numbers using Counting Sort by counting frequencies and placing elements in order.

Execution Table

Step	Operation	Array State	Count Array State	Output Array State	Pointer/Index Changes	Visual State
1	Find max value	[4, 2, 2, 8, 3, 3, 1]	-	-	-	Max value found: 8
2	Initialize count array	-	[0,0,0,0,0,0,0,0,0]	-	-	Count array size 9 with zeros
3	Count frequencies	[4, 2, 2, 8, 3, 3, 1]	[0,1,2,2,1,0,0,0,1]	-	-	Count of each number recorded
4	Cumulative count	-	[0,1,3,5,6,6,6,6,7]	-	-	Count array updated to cumulative counts
5	Build output (num=1)	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,5,6,6,6,6,7]	[1,0,0,0,0,0,0]	Place 1 at index 0
6	Build output (num=3)	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,4,6,6,6,6,7]	[1,0,0,0,3,0,0]	Place 3 at index 4
7	Build output (num=3)	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,3,6,6,6,6,7]	[1,0,0,3,3,0,0]	Place 3 at index 3
8	Build output (num=8)	[4, 2, 2, 8, 3, 3, 1]	[0,0,3,3,6,6,6,6,6]	[1,0,0,3,3,0,8]	Place 8 at index 6
9	Build output (num=2)	[4, 2, 2, 8, 3, 3, 1]	[0,0,2,3,6,6,6,6,6]	[1,0,2,3,3,0,8]	Place 2 at index 2
10	Build output (num=2)	[4, 2, 2, 8, 3, 3, 1]	[0,0,1,3,6,6,6,6,6]	[1,2,2,3,3,0,8]	Place 2 at index 1
11	Build output (num=4)	[4, 2, 2, 8, 3, 3, 1]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	Place 4 at index 5
12	Copy output to input	[1, 2, 2, 3, 3, 4, 8]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	-	Input array updated to sorted array
13	End	[1, 2, 2, 3, 3, 4, 8]	-	-	-	Sorting complete

💡 All elements placed in output array and copied back; sorting finished

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 11	Final
arr	[4, 2, 2, 8, 3, 3, 1]	[4, 2, 2, 8, 3, 3, 1]	[4, 2, 2, 8, 3, 3, 1]	[4, 2, 2, 8, 3, 3, 1]	[1, 2, 2, 3, 3, 4, 8]
count	-	[0,1,2,2,1,0,0,0,1]	[0,1,3,5,6,6,6,6,7]	[0,0,1,3,5,6,6,6,6]	[0,0,1,3,5,6,6,6,6]
output	-	-	-	[1,2,2,3,3,4,8]	[1,2,2,3,3,4,8]
max_val	8	8	8	8	8

Key Moments - 3 Insights

Why do we create the count array with size max_val + 1?

Because the count array needs an index for every number from 0 up to the maximum value in the input. This is shown in Step 2 where count array size is 9 for max_val 8.

Why do we iterate over the input array in reverse when building the output?

Iterating in reverse preserves the stability of the sort, meaning equal elements keep their original order. This is shown in Steps 5 to 11 where elements are placed from the end.

What does the cumulative count array represent?

It shows the position where each number should be placed in the output array. Step 4 updates count array to cumulative counts, which helps place elements correctly.

Visual Quiz - 3 Questions

Look at the execution table at Step 4, what is the cumulative count for number 3?

A 5

B 3

C 6

D 2

💡 Hint

Check the 'Count Array State' column at Step 4 in the execution table.

At which step does the output array first get the number 8 placed?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look at the 'Operation' and 'Output Array State' columns in the execution table for when 8 is placed.

If the input array had a maximum value of 5 instead of 8, how would the count array size change?

A It would be size 5

B It would be size 8

C It would be size 6

D It would be size 9

💡 Hint

Count array size is max_val + 1 as shown in Step 2.

Concept Snapshot

Counting Sort Algorithm:
- Find max value in array
- Create count array of size max+1
- Count frequency of each element
- Convert count array to cumulative counts
- Place elements in output array using counts
- Copy output back to original array
- Stable and efficient for small ranges

Full Transcript

Counting Sort works by first finding the maximum value in the input array to know the range. Then it creates a count array initialized with zeros. It counts how many times each number appears. Next, it changes the count array to hold cumulative counts, which tell where each number should go in the output. Then it builds the output array by placing each element at the correct position, iterating the input in reverse to keep order stable. Finally, it copies the sorted output back to the input array. This method is fast when the range of numbers is not too large.

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