Counting Sort Algorithm

1. Algorithm Explanation

Counting Sort is a non-comparative integer sorting algorithm. It assumes the input consists of elements in a known, limited range [0…K]. It works by:

1. Counting the occurrences of each distinct element in the input array into a "count" array of size K + 1.
2. Transforming the count array so that each position contains the cumulative count of elements ≤ that index.
3. Iterating the original array in reverse order, placing each element in its correct sorted position in an output array, and decrementing the corresponding count.

Time Complexity

• O(n + K), where n = number of elements, K = range of input values.

Space Complexity

• O(n + K): additional output array of size n plus count array of size K + 1.

---

2. Easy Problems

2.1. Sort an Array of Non-negative Integers

Given an array of non-negative integers, sort it in non-decreasing order.

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

void countingSort(vector<int>& A, int K) {
    int n = A.size();
    vector<int> count(K+1, 0), output(n);
    for (int x : A) count[x]++;
    for (int i = 1; i <= K; i++) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i--) {
        output[count[A[i]] - 1] = A[i];
        count[A[i]]--;
    }
    A = output;
}

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

2.2. Sort Characters in a String

Given a string of lowercase letters, return the sorted string.

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

string countingSortString(const string& s) {
    int K = 25; // 'a' to 'z'
    vector<int> count(K+1, 0);
    for (char c : s) count[c - 'a']++;
    string out;
    out.reserve(s.size());
    for (int i = 0; i <= K; i++) {
        out.append(count[i], char('a' + i));
    }
    return out;
}

int main() {
    string s = "dbcaab";
    cout << countingSortString(s);
    return 0;
}

---

3. Intermediate Problems

3.1. Sort Signed Integers (including negatives)

Extend Counting Sort to handle negative values by offsetting.

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

void countingSortSigned(vector<int>& A) {
    int n = A.size();
    int minV = *min_element(A.begin(), A.end());
    int maxV = *max_element(A.begin(), A.end());
    int range = maxV - minV + 1;
    vector<int> count(range, 0), output(n);
    for (int x : A) count[x - minV]++;
    for (int i = 1; i < range; i++) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i--) {
        output[count[A[i] - minV] - 1] = A[i];
        count[A[i] - minV]--;
    }
    A = output;
}

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

3.2. Counting Sort as Subroutine in Radix Sort

Use Counting Sort to sort numbers by each digit (LSD Radix Sort).

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

void countingSortByDigit(vector<int>& A, int exp) {
    int n = A.size();
    vector<int> count(10, 0), output(n);
    for (int x : A) count[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i--) {
        int idx = (A[i] / exp) % 10;
        output[count[idx] - 1] = A[i];
        count[idx]--;
    }
    A = output;
}

void radixSort(vector<int>& A) {
    int maxV = *max_element(A.begin(), A.end());
    for (int exp = 1; maxV / exp > 0; exp *= 10) {
        countingSortByDigit(A, exp);
    }
}

int main() {
    vector<int> A = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(A);
    for (int x : A) cout << x << " ";
    return 0;
}

---

4. Hard Problem

4.1. Sorting Queries of Frequencies (Top-K Frequent Elements)

Given an array, find the k most frequent elements. We can use Counting Sort on frequencies when the maximum frequency is bounded by n.

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

// Returns k most frequent elements
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;
    int n = nums.size();
    // bucket[i] contains all numbers with frequency i
    vector<vector<int>> bucket(n+1);
    for (auto &p : freq) {
        bucket[p.second].push_back(p.first);
    }
    vector<int> res;
    for (int i = n; i >= 1 && res.size() < k; --i) {
        for (int x : bucket[i]) {
            res.push_back(x);
            if (res.size() == k) break;
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    int k = 2;
    vector<int> ans = topKFrequent(nums, k);
    for (int x : ans) cout << x << " ";
    return 0;
}