Counting Sort Algorithm in DSA Java - 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 occurrences 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 that to place numbers in order.

Execution Sample

DSA Java

int[] arr = {4, 2, 2, 8, 3, 3, 1};
int max = 8;
int[] count = new int[max+1];
// Count occurrences
// Cumulative count
// Build output
// Copy back

Sorts the array by counting occurrences and placing elements in order.

Execution Table

Step	Operation	Count Array State	Output Array State	Input Array State	Notes
1	Initialize count array with zeros	[0, 0, 0, 0, 0, 0, 0, 0, 0]	[]	[4, 2, 2, 8, 3, 3, 1]	Count array size 9 (0 to 8)
2	Count occurrences of 4	[0, 0, 0, 0, 1, 0, 0, 0, 0]	[]	[4, 2, 2, 8, 3, 3, 1]	Increment count[4]
3	Count occurrences of 2	[0, 0, 2, 0, 1, 0, 0, 0, 0]	[]	[4, 2, 2, 8, 3, 3, 1]	Increment count[2] twice
4	Count occurrences of 8	[0, 0, 2, 0, 1, 0, 0, 0, 1]	[]	[4, 2, 2, 8, 3, 3, 1]	Increment count[8]
5	Count occurrences of 3	[0, 0, 2, 2, 1, 0, 0, 0, 1]	[]	[4, 2, 2, 8, 3, 3, 1]	Increment count[3] twice
6	Count occurrences of 1	[0, 1, 2, 2, 1, 0, 0, 0, 1]	[]	[4, 2, 2, 8, 3, 3, 1]	Increment count[1]
7	Modify count array to cumulative counts	[0, 1, 3, 5, 6, 6, 6, 6, 7]	[]	[4, 2, 2, 8, 3, 3, 1]	Each count[i] = count[i] + count[i-1]
8	Place 1 in output	[0, 0, 3, 5, 6, 6, 6, 6, 7]	[1, _, _, _, _, _, _]	[4, 2, 2, 8, 3, 3, 1]	Place at index count[1]-1=0, decrement count[1]
9	Place 3 in output	[0, 0, 3, 4, 6, 6, 6, 6, 7]	[1, _, _, _, 3, _, _]	[4, 2, 2, 8, 3, 3, 1]	Place at index count[3]-1=4, decrement count[3]
10	Place 3 in output	[0, 0, 3, 3, 6, 6, 6, 6, 7]	[1, _, _, 3, 3, _, _]	[4, 2, 2, 8, 3, 3, 1]	Place at index count[3]-1=3, decrement count[3]
11	Place 8 in output	[0, 0, 3, 3, 6, 6, 6, 6, 6]	[1, _, _, 3, 3, _, 8]	[4, 2, 2, 8, 3, 3, 1]	Place at index count[8]-1=6, decrement count[8]
12	Place 2 in output	[0, 0, 2, 3, 6, 6, 6, 6, 6]	[1, _, 2, 3, 3, _, 8]	[4, 2, 2, 8, 3, 3, 1]	Place at index count[2]-1=2, decrement count[2]
13	Place 2 in output	[0, 0, 1, 3, 6, 6, 6, 6, 6]	[1, 2, 2, 3, 3, _, 8]	[4, 2, 2, 8, 3, 3, 1]	Place at index count[2]-1=1, decrement count[2]
14	Place 4 in output	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[4, 2, 2, 8, 3, 3, 1]	Place at index count[4]-1=5, decrement count[4]
15	Copy output array 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]	Input array sorted
16	End	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[1, 2, 2, 3, 3, 4, 8]	Sorting complete

💡 All elements placed in output and copied back, input array sorted

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 15	Final
count	[0,0,0,0,0,0,0,0,0]	[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]
input	[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]	[1,2,2,3,3,4,8]

Key Moments - 3 Insights

Why do we need to create a count array of size max+1?

Because the count array indexes represent all possible values from 0 to max. This lets us count occurrences directly by value, as shown in execution_table rows 1 and 2.

Why do we modify the count array to cumulative counts?

Cumulative counts tell us the final position of each element in the output array. This is shown in execution_table row 7, enabling correct placement in rows 8-14.

Why do we place elements in output array by iterating input from right to left?

Placing from right to left keeps the sort stable (preserves order of equal elements). The execution_table rows 8-14 show placement using count array indexes decreasing.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the cumulative count for value 3?

A 2

B 4

C 5

D 6

💡 Hint

Check the 'Count Array State' column at step 7 for index 3

At which step does the count for value 2 decrease from 3 to 2?

A Step 11

B Step 12

C Step 13

D Step 14

💡 Hint

Look at 'Count Array State' column changes for index 2 between steps 11 and 13

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

A It would stay the same

B It would increase by 1

C It would decrease by 1

D It would double

💡 Hint

Count array size depends on max value, not minimum or number of elements

Concept Snapshot

Counting Sort Algorithm:
- Create count array sized max+1
- Count occurrences of each element
- Convert counts to cumulative counts
- Place elements in output using counts
- Copy output back to input
- Stable and efficient for small range integers

Full Transcript

Counting sort works by counting how many times each number appears in the input array. First, we find the maximum value to know the size of the count array. Then, we create a count array initialized with zeros. We count each element's occurrences by incrementing the count at the index equal to the element's value. Next, we modify the count array to hold cumulative counts, which tell us the positions of elements in the sorted output. We then build the output array by placing each element at the correct position using the count array, iterating from right to left to keep the sort stable. Finally, we copy the output array back to the input array, completing the sort. This method is efficient for sorting integers within a small range.

Practice

1. What is the main idea behind the Counting Sort algorithm?

easy

A. Count the occurrences of each element and use counts to place elements in order

B. Compare each element with every other element to sort

C. Divide the array into halves and sort recursively

D. Swap adjacent elements if they are in wrong order repeatedly

Solution

1. Step 1: Understand Counting Sort principle

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

2. Step 2: Use counts to place elements

   These counts help to place elements directly in the sorted output without comparisons.

3. Final Answer:

   Count the occurrences of each element and use counts to place elements in order -> Option A

4. Quick Check:

   Counting occurrences = main idea [OK]

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

Common Mistakes:

• Thinking Counting Sort compares elements
• Confusing Counting Sort with Quick Sort or Merge Sort
• Assuming Counting Sort works well with all data types

2. Which of the following is the correct way to declare the count array for Counting Sort in Java if the input values range from 0 to 9?

easy

A. int[] count = new int[10];

B. int count[] = new int(10);

C. int count = new int[10];

D. int[] count = new int();

Solution

1. Step 1: Understand Java array declaration syntax

   In Java, arrays are declared with type[], name = new type[size];

2. Step 2: Check each option for correct syntax

   int[] count = new int[10]; uses correct syntax: int[] count = new int[10]; int count[] = new int(10); uses parentheses instead of brackets, invalid. int count = new int[10]; misses brackets on left side. int[] count = new int(); misses size in brackets.

3. Final Answer:

   int[] count = new int[10]; -> Option A

4. Quick Check:

   Correct Java array syntax = int[] count = new int[10]; [OK]

Hint: Use square brackets and specify size for arrays in Java [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Not specifying array size when creating
• Incorrect placement of brackets in declaration

3. What will be the output of the following Java code snippet using Counting Sort?

int[] arr = {4, 2, 2, 8, 3, 3, 1};
int max = 8;
int[] count = new int[max + 1];
for (int num : arr) {
    count[num]++;
}
int index = 0;
for (int i = 0; i <= max; i++) {
    while (count[i] > 0) {
        arr[index++] = i;
        count[i]--;
    }
}
System.out.println(java.util.Arrays.toString(arr));

medium

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

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

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

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

Solution

1. Step 1: Count occurrences of each number

   Count array after loop: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1, others=0.

2. Step 2: Rebuild sorted array using counts

   Fill arr with 1 once, 2 twice, 3 twice, 4 once, 8 once in order.

3. Final Answer:

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

4. Quick Check:

   Sorted array matches [1, 2, 2, 3, 3, 4, 8] [OK]

Hint: Count frequencies, then overwrite array in order [OK]

Common Mistakes:

• Not initializing count array size correctly
• Forgetting to decrement count during placement
• Printing original array without sorting

4. Identify the error in this Counting Sort code snippet and select the correct fix:

int[] arr = {3, 1, 2};
int max = 3;
int[] count = new int[max];
for (int num : arr) {
    count[num]++;
}

medium

A. Change 'count[num]++' to 'count[num - 1]++' to fix indexing

B. Change 'int[] count = new int[max];' to 'int[] count = new int[max + 1];' to include max index

C. Initialize count array with size 'max - 1' instead of 'max' to save space

D. No error, code is correct as is

Solution

1. Step 1: Check count array size for indexing

   Array 'count' size is max=3, so indices 0,1,2 are valid but input has value 3 which is out of bounds.

2. Step 2: Fix count array size to include max index

   Size should be max+1=4 to allow index 3 access safely.

3. Final Answer:

   Change 'int[] count = new int[max];' to 'int[] count = new int[max + 1];' to include max index -> Option B

4. Quick Check:

   Array size must cover max value index [OK]

Hint: Count array size = max value + 1 to avoid index errors [OK]

Common Mistakes:

• Using count array size equal to max value only
• Adjusting indices incorrectly instead of size
• Ignoring ArrayIndexOutOfBoundsException

5. Given an array arr = {5, 3, 0, 2, 3, 0, 1}, how would you modify the Counting Sort algorithm to sort it if the input can contain negative numbers as well? Choose the best approach.

hard

A. Use a hash map instead of an array for counts

B. Ignore negative numbers as Counting Sort cannot handle them

C. Shift all numbers by adding the absolute value of the minimum negative number before counting

D. Sort only the positive numbers and append negatives at the end

Solution

1. Step 1: Understand Counting Sort limitation with negatives

   Counting Sort uses array indices as counts, so negative indices are invalid.

2. Step 2: Shift values to non-negative range

   Find minimum value, add its absolute value to all elements to make them non-negative, then apply Counting Sort.

3. Final Answer:

   Shift all numbers by adding the absolute value of the minimum negative number before counting -> Option C

4. Quick Check:

   Shift negatives to positive range for Counting Sort [OK]

Hint: Add offset to handle negatives before counting [OK]

Common Mistakes:

• Trying to use negative indices in count array
• Ignoring negative values in input
• Using incorrect data structures without reason