Counting Sort Algorithm in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a Small Array

What is the output of the following C++ code that uses counting sort on the given array?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    vector<int> count(max_val + 1, 0);
    for (int num : arr) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

int main() {
    vector<int> data = {4, 2, 2, 8, 3, 3, 1};
    countingSort(data);
    for (int num : data) {
        cout << num << " ";
    }
    return 0;
}

A 1 2 3 4 8

B 8 4 3 3 2 2 1

C 1 2 2 3 3 4 8

D 1 1 2 2 3 3 4 8

💡 Hint

Counting sort counts how many times each number appears and then reconstructs the array in order.

The counting sort algorithm counts the occurrences of each number and then places them back in sorted order. The input array {4, 2, 2, 8, 3, 3, 1} is sorted to {1, 2, 2, 3, 3, 4, 8}.

🧠 Conceptual

intermediate

Counting Sort Stability Property

Which statement correctly describes the stability property of counting sort?

A Counting sort is stable because it preserves the relative order of equal elements.

B Counting sort is unstable because it rearranges equal elements arbitrarily.

C Counting sort is stable only if the input array is already sorted.

D Counting sort is unstable because it uses a hash map internally.

💡 Hint

Stability means equal elements keep their original order after sorting.

Counting sort is stable because it places elements in the output array in the order they appear in the input, preserving relative order of equal elements.

❓ Predict Output

advanced

Counting Sort with Negative Numbers

What will be the output of this modified counting sort code that attempts to sort an array with negative numbers?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int>& arr) {
    int min_val = *min_element(arr.begin(), arr.end());
    int max_val = *max_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1;
    vector<int> count(range, 0);
    for (int num : arr) {
        count[num - min_val]++;
    }
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min_val;
            count[i]--;
        }
    }
}

int main() {
    vector<int> data = {-5, -10, 0, -3, 8, 5, -1, 10};
    countingSort(data);
    for (int num : data) {
        cout << num << " ";
    }
    return 0;
}

A -10 -5 -3 -1 0 5 8 10

B -5 -10 -3 -1 0 5 8 10

C -10 -5 -3 -1 0 5 8

D 0 5 8 10 -10 -5 -3 -1

💡 Hint

Adjusting counts by minimum value allows sorting negative numbers.

By shifting the index using min_val, counting sort can handle negative numbers correctly, resulting in sorted output.

🔧 Debug

advanced

Identify the Bug in Counting Sort Implementation

What error will occur when running this counting sort code snippet?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    vector<int> count(max_val, 0);
    for (int num : arr) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

int main() {
    vector<int> data = {1, 4, 1, 2, 7, 5, 2};
    countingSort(data);
    for (int num : data) {
        cout << num << " ";
    }
    return 0;
}

A Output: 1 1 2 2 4 5 7

B Runtime error: out_of_range exception

C Compilation error: missing #include <algorithm>

D Output: 1 2 4 5 7

💡 Hint

Check the size of the count vector and the indexing inside the loop.

The count vector size is max_val but the loop accesses count[max_val], causing out_of_range error.

🚀 Application

expert

Counting Sort for Sorting Characters by ASCII Values

Given the following code to sort characters by their ASCII values using counting sort, what is the output?

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void countingSortChars(string& s) {
    int max_val = 127; // ASCII max for standard chars
    vector<int> count(max_val + 1, 0);
    for (char c : s) {
        count[(int)c]++;
    }
    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            s[index++] = (char)i;
            count[i]--;
        }
    }
}

int main() {
    string text = "dsaAlgorithm123";
    countingSortChars(text);
    cout << text << endl;
    return 0;
}

A

123AGadhilmort

B 123AdGahilmort

C 123AGadhilmort\n

D 123Aadghilmorst

💡 Hint

Counting sort sorts characters by their ASCII codes in ascending order.

The characters are sorted by ASCII values resulting in '123Aadghilmorst'.

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