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'.