Why Counting Sort Algorithm in DSA C++?

The Big Idea

What if you could sort thousands of items instantly just by counting them first?

The Scenario

Imagine you have a big box of colored balls, and you want to arrange them by color quickly. If you try to pick each ball and compare it with every other ball to find its place, it will take a very long time.

The Problem

Sorting by comparing each ball to others is slow and tiring. It can take a lot of time, especially if you have many balls. Also, it is easy to make mistakes when comparing many items one by one.

The Solution

Counting Sort solves this by counting how many balls of each color you have first. Then, it uses these counts to place each ball directly in the right order without comparing them one by one. This makes sorting very fast and simple.

Before vs After

✗ Before

for (int i = 0; i < n - 1; i++) {
  for (int j = i + 1; j < n; j++) {
    if (arr[i] > arr[j]) {
      std::swap(arr[i], arr[j]);
    }
  }
}

✓ After

int count[maxValue + 1] = {0};
for (int i = 0; i < n; i++) {
  count[arr[i]]++;
}
int index = 0;
for (int i = 0; i <= maxValue; i++) {
  while (count[i]-- > 0) {
    arr[index++] = i;
  }
}

What It Enables

Counting Sort enables lightning-fast sorting when you know the range of values, making tasks like organizing or searching much easier.

Real Life Example

Think about sorting exam scores from 0 to 100. Counting Sort quickly counts how many students got each score and then lists the scores in order without comparing each student's score to others.

Key Takeaways

Manual comparison sorting is slow and error-prone for large data.

Counting Sort counts occurrences to sort efficiently without direct comparisons.

This method is perfect when sorting numbers within a known 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 each element directly into 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 = Count the occurrences of each element and use counts to place elements in order [OK]

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

Common Mistakes:

• Thinking counting sort compares elements
• Confusing counting sort with merge sort
• Assuming counting sort works on any data type

2. Which of the following is the correct way to declare the count array for counting sort in C++ if the input values range from 0 to 9?

easy

A. int count[9] = {0};

B. int count[10] = {0};

C. int count[11] = {0};

D. int count[] = {0};

Solution

1. Step 1: Determine size of count array

   Input values range from 0 to 9, so we need 10 slots (0 through 9).

2. Step 2: Declare count array with size 10

   Using int count[10] = {0}; initializes all counts to zero for indices 0 to 9.

3. Final Answer:

   int count[10] = {0}; -> Option B

4. Quick Check:

   Array size = max value + 1 = 10 [OK]

Hint: Count array size = max element value + 1 [OK]

Common Mistakes:

• Using size 9 instead of 10
• Not initializing count array to zero
• Declaring count array without size

3. What is the output of the following C++ code snippet using counting sort on array arr = {4, 2, 2, 8, 3, 3, 1}?

void countingSort(int arr[], int n) {
    int output[n];
    int count[9] = {0};
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
    for (int i = 1; i < 9; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    return 0;
}

medium

A. 2 2 3 3 4 8 1

B. 8 4 3 3 2 2 1

C. 1 2 3 4 8 2 3

D. 1 2 2 3 3 4 8

Solution

1. Step 1: Count frequencies and cumulative counts

   Count array after counting: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1; cumulative sums give positions.

2. Step 2: Place elements in output using counts

   Elements placed in output array in sorted order: 1 2 2 3 3 4 8.

3. Final Answer:

   1 2 2 3 3 4 8 -> Option D

4. Quick Check:

   Sorted array = 1 2 2 3 3 4 8 [OK]

Hint: Counting sort output is sorted input array [OK]

Common Mistakes:

• Not using cumulative counts correctly
• Placing elements in wrong order
• Using wrong count array size

4. Identify the bug in this counting sort code snippet and choose the correct fix:

void countingSort(int arr[], int n) {
    int output[n];
    int count[10] = {0};
    for (int i = 0; i <= n; i++)
        count[arr[i]]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

medium

A. Initialize output array with zeros

B. Increase count array size to 11

C. Change loop to for (int i = 0; i < n; i++) in first for loop

D. Change second for loop to start from i = 0

Solution

1. Step 1: Check loop bounds in counting frequencies

   The first for loop uses i <= n, which accesses arr[n] out of bounds (indexing error).

2. Step 2: Fix loop condition to i < n

   Changing to i < n prevents out-of-bounds access and correctly counts frequencies.

3. Final Answer:

   Change loop to for (int i = 0; i < n; i++) in first for loop -> Option C

4. Quick Check:

   Loop bounds must be less than n to avoid errors [OK]

Hint: Loop over array indices from 0 to n-1 [OK]

Common Mistakes:

• Using <= n instead of < n in loops
• Ignoring array out-of-bounds errors
• Changing unrelated loops unnecessarily

5. Given an array arr = {5, 3, 0, 2, 3, 5, 1, 4} with values ranging from 0 to 5, how would you modify the counting sort algorithm to sort this array in descending order?

hard

A. After computing cumulative counts, iterate from highest to lowest index to place elements in output

B. Reverse the input array before sorting with normal counting sort

C. Use a max heap instead of counting sort for descending order

D. Sort normally and then reverse the output array after counting sort completes

Solution

1. Step 1: Understand normal counting sort placement

   Normal counting sort places elements from lowest to highest using cumulative counts.

2. Step 2: Modify placement to iterate from highest to lowest

   To sort descending, iterate counts from max to min and place elements accordingly in output.

3. Final Answer:

   After computing cumulative counts, iterate from highest to lowest index to place elements in output -> Option A

4. Quick Check:

   Reverse iteration in placement = descending sort [OK]

Hint: Reverse placement loop for descending order [OK]

Common Mistakes:

• Just reversing input without changing counting logic
• Using other sorting algorithms instead of modifying counting sort
• Reversing output after sorting without adjusting counts