Counting Sort Algorithm in DSA Java - Deep Dive

Overview - Counting Sort Algorithm

What is it?

Counting Sort is a way to sort a list of numbers by counting how many times each number appears. It works best when the numbers are within a small range. Instead of comparing numbers directly, it uses their counts to place them in order. This method is very fast for certain types of data.

Why it matters

Without Counting Sort, sorting numbers with many repeats or within a small range would take longer using usual methods. Counting Sort solves this by using counting, which can be much faster. This helps in real-life tasks like organizing test scores or sorting colors in images quickly. Without it, some sorting tasks would be slower and less efficient.

Where it fits

Before learning Counting Sort, you should understand basic sorting methods like Bubble Sort or Selection Sort. After Counting Sort, you can explore more advanced sorting algorithms like Radix Sort or Bucket Sort, which build on similar ideas.

Mental Model

Core Idea

Counting Sort sorts numbers by counting how many times each number appears and then placing them in order based on these counts.

Think of it like...

Imagine you have a box of colored balls and you want to arrange them by color. Instead of sorting one by one, you count how many balls of each color you have, then line them up color by color using those counts.

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

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

Cumulative count:
Index: 0 1 2 3 4 5 6 7 8
Count: 0 1 3 5 6 6 6 6 7

Sorted output: [1, 2, 2, 3, 3, 4, 8]

Build-Up - 7 Steps

1

Foundation

Understanding Counting Basics

Concept: Counting how many times each number appears in a list.

Given a list of numbers, we create a separate list (count array) where each position corresponds to a number in the range. We increase the count at that position every time the number appears in the input list.

Result

For input [2, 3, 2, 1], count array might look like [0,1,2,1] meaning 1 appears once, 2 appears twice, 3 appears once.

Understanding counting is the foundation of Counting Sort because it replaces direct comparisons with frequency tracking.

2

Foundation

Range and Count Array Setup

Concept: Setting up the count array size based on the input range.

To count correctly, we find the smallest and largest numbers in the input. Then we create a count array sized to cover this range. This ensures every number has a place to count its occurrences.

Result

For input [4, 2, 8], range is 2 to 8, so count array size is 7 (indexes 2 to 8).

Knowing the range is crucial to allocate the right size count array and avoid errors or wasted space.

3

Intermediate

Building the Cumulative Count

🤔Before reading on: do you think the count array alone is enough to place numbers in order, or do we need another step? Commit to your answer.

Concept: Transforming the count array into a cumulative count array to find positions.

We update the count array so each position holds the sum of counts up to that index. This cumulative count tells us the position where each number should go in the sorted output.

Result

If count array is [0,1,2,1], cumulative count becomes [0,1,3,4].

Cumulative counts link counts to positions, enabling direct placement of numbers without comparisons.

4

Intermediate

Placing Elements in Sorted Order

🤔Before reading on: when placing elements using cumulative counts, should we process the input from start to end or end to start? Commit to your answer.

Concept: Using cumulative counts to place each element in the correct position in the output array.

We go through the input array backward. For each element, we look up its cumulative count to find its position in the output array, place it there, and then decrease the count by one.

Result

Input [4, 2, 2, 8, 3, 3, 1] becomes sorted output [1, 2, 2, 3, 3, 4, 8].

Processing backward preserves stability, meaning equal elements keep their original order.

5

Intermediate

Handling Stability in Sorting

Concept: Ensuring that equal elements appear in the output in the same order as in the input.

By placing elements from the end of the input array using cumulative counts, Counting Sort keeps the relative order of equal elements. This is important when sorting complex data with keys.

Result

If input has two '3's, their order in output matches input order.

Stability is key for multi-level sorting and preserving data relationships.

6

Advanced

Time and Space Complexity Analysis

🤔Before reading on: do you think Counting Sort always uses less memory than comparison sorts? Commit to your answer.

Concept: Understanding how Counting Sort's speed and memory use depend on input size and range.

Counting Sort runs in O(n + k) time, where n is input size and k is range size. It uses extra space proportional to k. If k is small compared to n, Counting Sort is very fast. But if k is large, it uses more memory and can be slower.

Result

For input size 100 and range 10, Counting Sort is efficient. For input size 100 and range 1,000,000, it uses a lot of memory.

Knowing complexity helps decide when Counting Sort is practical or when other sorts are better.

7

Expert

Counting Sort in Real-World Systems

🤔Before reading on: do you think Counting Sort is used alone in complex systems or combined with other algorithms? Commit to your answer.

Concept: How Counting Sort is combined with other algorithms and optimized in practice.

Counting Sort is often used as a subroutine in Radix Sort for sorting digits or characters. It is optimized by limiting range or using in-place variants. Real systems use it when data fits its strengths, like sorting integers or colors quickly.

Result

Counting Sort helps Radix Sort achieve linear time sorting for large datasets with fixed digit sizes.

Understanding Counting Sort's role in bigger algorithms reveals its practical power beyond simple sorting.

Under the Hood

Counting Sort creates a frequency array that counts occurrences of each number. Then it transforms this into a cumulative count array that tells where each number should be placed in the output. By iterating backward through the input and placing elements using these counts, it builds a sorted array without comparing elements directly.

Why designed this way?

Counting Sort was designed to avoid costly comparisons by using counting, which is faster when the input range is small. It trades extra memory for speed. Alternatives like comparison sorts have a lower bound of O(n log n), but Counting Sort can achieve O(n) under the right conditions.

Input Array
  ↓
Count Array (frequency)
  ↓ (prefix sum)
Cumulative Count Array
  ↓ (backward iteration)
Sorted Output Array

Myth Busters - 3 Common Misconceptions

Quick: Does Counting Sort work well for sorting floating-point numbers? Commit to yes or no.

Common Belief: Counting Sort can sort any type of numbers efficiently.

Reality: Counting Sort only works well for integers or discrete values within a small range, not for floating-point numbers with many decimals.

Why it matters: Using Counting Sort on floating-point numbers can lead to incorrect results or huge memory use, causing program failures.

Quick: Is Counting Sort always faster than Quick Sort? Commit to yes or no.

Common Belief: Counting Sort is always faster than comparison-based sorts like Quick Sort.

Reality: Counting Sort is faster only when the range of input values is small compared to the number of elements. Otherwise, Quick Sort or other algorithms may be faster.

Why it matters: Choosing Counting Sort blindly can waste memory and time on large ranges, hurting performance.

Quick: Does Counting Sort change the order of equal elements? Commit to yes or no.

Common Belief: Counting Sort does not preserve the order of equal elements.

Reality: Counting Sort is stable and preserves the order of equal elements if implemented correctly by placing elements backward.

Why it matters: Incorrect assumptions about stability can lead to bugs in multi-level sorting tasks.

Expert Zone

1

Counting Sort's stability depends on processing the input array backward during placement, a detail often missed.

2

The memory overhead of Counting Sort can be reduced by shifting the count array indices when the input range does not start at zero.

3

Counting Sort can be adapted for sorting objects by keys by counting keys and rearranging objects, not just numbers.

When NOT to use

Avoid Counting Sort when the input range is very large compared to the number of elements, or when sorting data types without discrete integer keys. Use comparison-based sorts like Merge Sort or Quick Sort instead.

Production Patterns

Counting Sort is commonly used as a subroutine in Radix Sort for sorting integers or strings by digit or character. It is also used in graphics for color sorting and in systems where stable, linear-time sorting of small-range integers is needed.

Connections

Radix Sort

Counting Sort is used as a stable subroutine within Radix Sort to sort digits or characters.

Understanding Counting Sort helps grasp how Radix Sort achieves efficient sorting by processing digits step-by-step.

Histogram

Counting Sort's count array is essentially a histogram of input values.

Knowing histograms in statistics helps understand how Counting Sort summarizes data frequencies for sorting.

Inventory Management

Counting Sort's counting and placement resembles tracking and organizing stock items by quantity.

Seeing Counting Sort like inventory counting reveals how organizing by quantity can speed up sorting and retrieval.

Common Pitfalls

#1 Using Counting Sort on data with a very large range wastes memory.

Wrong approach:

int max = 1000000;
int[] count = new int[max + 1]; // huge array for small input
// rest of counting sort code

Correct approach:

Find actual max and min from input to limit count array size:
int min = findMin(input);
int max = findMax(input);
int[] count = new int[max - min + 1];

Root cause:

Not considering input range leads to unnecessarily large count arrays and memory waste.

#2 Placing elements forward in output breaks stability.

Wrong approach:

for (int i = 0; i < input.length; i++) {
output[count[input[i]] - 1] = input[i];
count[input[i]]--;
}

Correct approach:

for (int i = input.length - 1; i >= 0; i--) {
output[count[input[i]] - 1] = input[i];
count[input[i]]--;
}

Root cause:

Not iterating backward during placement causes equal elements to reorder incorrectly.

#3 Assuming Counting Sort works for floating-point numbers directly.

Wrong approach:

Counting Sort on array like [1.2, 3.4, 2.2] without conversion or mapping.

Correct approach:

Map floating-point numbers to integers by scaling or use comparison-based sorts instead.

Root cause:

Counting Sort requires discrete integer keys; floating points need special handling.

Key Takeaways

Counting Sort sorts by counting occurrences and using these counts to place elements directly, avoiding comparisons.

It is very fast and stable when the input range is small compared to the number of elements.

The algorithm uses extra memory proportional to the input range, so large ranges can make it inefficient.

Stability is preserved by placing elements from the end of the input array using cumulative counts.

Counting Sort is a key building block for more advanced algorithms like Radix Sort and is widely used in practice for sorting integers and categorical data.

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