Counting Sort Algorithm in DSA Java

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by counting how many balls of each color you have, then lining them up color by color based on those counts.

Unsorted array:
[4] -> [2] -> [2] -> [8] -> [3] -> [3] -> [1] -> null

Count array (index = number, value = count):
Index: 0 1 2 3 4 5 6 7 8
Count: 0 1 2 2 1 0 0 0 1

Sorted array:
[1] -> [2] -> [2] -> [3] -> [3] -> [4] -> [8] -> null

Dry Run Walkthrough

Input: array: [4, 2, 2, 8, 3, 3, 1]

Goal: Sort the array in ascending order using counting sort

Step 1: Count how many times each number appears

Count array: index 0 to 8 with counts: 0 1 2 2 1 0 0 0 1

Why: We need to know the frequency of each number to place them correctly

Step 2: Modify count array to hold cumulative counts

Count array after cumulative sum: 0 1 3 5 6 6 6 6 7

Why: Cumulative counts tell us the positions where each number ends in the sorted array

Step 3: Place each element from original array into output array using count array

Output array being filled step by step:
[_, _, _, _, _, _, _]
Place 1 at index 0 -> [1, _, _, _, _, _, _]
Place 3 at index 4 -> [1, _, _, _, 3, _, _]
Place 3 at index 3 -> [1, _, _, 3, 3, _, _]
Place 8 at index 6 -> [1, _, _, 3, 3, _, 8]
Place 2 at index 2 -> [1, _, 2, 3, 3, _, 8]
Place 2 at index 1 -> [1, 2, 2, 3, 3, _, 8]
Place 4 at index 5 -> [1, 2, 2, 3, 3, 4, 8]

Why: We use counts to find exact positions for each number in sorted order

Result:

Sorted array: [1] -> [2] -> [2] -> [3] -> [3] -> [4] -> [8] -> null

Annotated Code

DSA Java

import java.util.Arrays;

public class CountingSort {
    // Function to perform counting sort on input array
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return; // handle empty array

        // Find max value to size count array
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num; // find max number
        }

        int[] count = new int[max + 1]; // count array to store frequency

        // Count frequency of each number
        for (int num : arr) {
            count[num]++;
        }

        // Modify count array to store cumulative counts
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        int[] output = new int[arr.length]; // output array to store sorted result

        // Place elements into output array in sorted order
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            count[num]--; // decrement count for this number
            output[count[num]] = num; // place number at correct position
        }

        // Copy sorted elements back to original array
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        // Print sorted array
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

for (int num : arr) { if (num > max) max = num; // find max number }

Find the largest number to size count array

for (int num : arr) { count[num]++; // count frequency }

Count how many times each number appears

for (int i = 1; i < count.length; i++) { count[i] += count[i - 1]; // cumulative counts }

Convert counts to cumulative counts for positions

for (int i = arr.length - 1; i >= 0; i--) { count[num]--; output[count[num]] = num; // place in output }

Place elements in output array in sorted order using counts

for (int i = 0; i < arr.length; i++) { arr[i] = output[i]; // copy back }

Copy sorted output back to original array

Output

1 2 2 3 3 4 8 

Complexity Analysis

Time: O(n + k) because we count frequencies in O(n) and process counts in O(k), where n is array size and k is max value

Space: O(n + k) because we use output array of size n and count array of size k+1

vs Alternative: Compared to comparison sorts like quicksort O(n log n), counting sort is faster when k (max value) is not much larger than n

Edge Cases

empty array

function returns immediately without error

DSA Java

if (arr.length == 0) return;

array with all same elements

count array counts one number, output is same as input

DSA Java

for (int num : arr) { count[num]++; }

array with single element

count array size 1, output same as input

DSA Java

if (arr.length == 0) return;

When to Use This Pattern

When you need to sort integers within a known small range quickly without comparisons, reach for counting sort because it uses counting and positions to sort in linear time.

Common Mistakes

Mistake: Not using cumulative counts to find correct positions
Fix: Add cumulative sum step to count array before placing elements

Mistake: Placing elements in output array from start to end causing unstable sort
Fix: Place elements from end to start to maintain stability

Mistake: Not copying sorted output back to original array
Fix: Copy output array elements back to input array after sorting

Summary

Counting sort sorts numbers by counting their occurrences and using these counts to place them in order.

Use counting sort when sorting integers with a small range efficiently and stably.

The key insight is to use counts to find exact positions without comparing elements.

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