Counting Sort Algorithm in DSA C++ - 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

↓

Place elements into output array using count array

↓

Copy output array back to input array

↓

Done

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

Execution Sample

DSA C++

int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = 7;
countingSort(arr, n);

Sorts the array {4, 2, 2, 8, 3, 3, 1} using counting sort.

Execution Table

Step	Operation	Count Array State	Output Array State	Input Array State
1	Find max value in arr	N/A	N/A	[4, 2, 2, 8, 3, 3, 1]
2	Create count array of size max+1 (9)	[0, 0, 0, 0, 0, 0, 0, 0, 0]	N/A	[4, 2, 2, 8, 3, 3, 1]
3	Count frequency of each element	[0, 1, 2, 2, 1, 0, 0, 0, 1]	N/A	[4, 2, 2, 8, 3, 3, 1]
4	Modify count array to cumulative counts	[0, 1, 3, 5, 6, 6, 6, 6, 7]	N/A	[4, 2, 2, 8, 3, 3, 1]
5	Place elements into output array (process from right to left)	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[4, 2, 2, 8, 3, 3, 1]
6	Copy output array back to input array	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[1, 2, 2, 3, 3, 4, 8]
7	End of sorting	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[1, 2, 2, 3, 3, 4, 8]

💡 All elements placed in sorted order, input array updated.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	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	N/A	[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	N/A	N/A	N/A	[1, 2, 2, 3, 3, 4, 8]	[1, 2, 2, 3, 3, 4, 8]

Key Moments - 3 Insights

Why do we process the input array from right to left when placing elements into the output array?

Processing from right to left ensures stable sorting by placing duplicates in correct order, as shown in step 5 of the execution_table.

Why do we need to modify the count array to cumulative counts?

Cumulative counts tell the exact position of each element in the output array, as seen in step 4 where count array changes to cumulative sums.

What happens if the input array contains negative numbers?

Counting sort as shown only works with non-negative integers because count array indices represent values; negative numbers would cause invalid indexing.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the frequency count of number 3?

A 1

B 3

C 2

D 0

💡 Hint

Check the count array state at step 3 in execution_table, index 3 shows frequency.

At which step does the count array become cumulative?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the count array state changes in execution_table rows for step 4.

If the input array had an extra element '0', how would the count array size change?

A It would increase by 1

B It would stay the same

C It would decrease by 1

D It would double

💡 Hint

Count array size depends on max value + 1, adding 0 does not increase max value.

Concept Snapshot

Counting Sort Algorithm:
- Find max value in input
- Create count array size max+1
- Count frequencies of each element
- Convert count array to cumulative counts
- Place elements in output using count array
- Copy output back to input
- Works only for non-negative integers

Full Transcript

Counting sort works by counting how many times each number appears in the input array. First, it finds the maximum value to know how big the count array should be. Then it creates and initializes the count array with zeros. Next, it counts the frequency of each number in the input. After that, it changes the count array to cumulative counts, which tell where each number should go in the output array. Then it places each element from the input into the output array by looking up positions in the count array, processing from right to left to keep the order stable. Finally, it copies the sorted output back to the input array. This method only works for non-negative integers because the count array uses values as indices.