I. In-Class Exercises

Programming Exercises

1. Counting Sort 1: L2171
2. Counting Sort 2: L2172
3. Spring Outing: L2173

II. Knowledge Summary

Counting Sort: Core Concept

Counting Sort is used to sort a collection of data stored in a linear structure. It is a non-comparison sorting algorithm that is especially suited for scenarios where the data range is small.

Counting Sort is a value-domain-based sorting algorithm. It determines the sorted position of the i-th element by counting how many elements are greater or smaller than it. Counting Sort uses extra storage space to track the frequency of each element -- it is a space-for-time algorithm.

Simplified Counting Sort

Before learning the full version of Counting Sort, let's look at a simplified version. This version does not require prefix sums, has shorter code, and is easier to understand.

Core idea: Count how many times each value appears, then output each value the corresponding number of times in order.

1#include <bits/stdc++.h>
2using namespace std;
3
4int cnt[105] = {};
5
6int main() {
7        int n, x;
8        cin >> n;
9        for (int i = 0; i < n; ++i) {
10                cin >> x;
11                ++cnt[x];
12        }
13        for (int i = 1; i <= 100; ++i) {
14                for (int j = 0; j < cnt[i]; ++j) {
15                        cout << i << " ";
16                }
17        }
18        return 0;
19}

Limitations of the simplified version:

• It can only output the sorted values -- it cannot track the original position of elements
• If you need to sort structs or multi-attribute data (e.g., sorting students by score), the simplified version is insufficient
• It is not a stable sort -- it cannot preserve the original relative order of equal values

Therefore, the simplified version works when the problem only requires outputting sorted values. When stable sorting or handling more complex data is needed, use the full version below.

Counting Sort: Ascending Order

How ascending Counting Sort works:

1. Count how many times each value appears
2. Compute the prefix sum of the counts
3. Determine each value's rank based on the prefix sum

Here is the full implementation for ascending order:

1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9        int n;
10        cin >> n;
11        for (int i = 0; i < n; ++i) {
12                cin >> arr[i];
13                ++cnt[arr[i]];
14        }
15        for (int i = 2; i <= 100; ++i) {
16                cnt[i] += cnt[i - 1];
17        }
18        for (int i = n - 1; i >= 0; --i) {
19                ans[--cnt[arr[i]]] = arr[i];
20        }
21        for (int i = 0; i < n; ++i) {
22                cout << ans[i] << (i + 1 == n ? "\n" : " ");
23        }
24
25        return 0;
26}

Counting Sort: Descending Order

How descending Counting Sort works:

1. Count how many times each value appears
2. Compute the suffix sum of the counts
3. Determine each value's rank based on the suffix sum

Here is the full implementation for descending order:

1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9        int n;
10        cin >> n;
11        for (int i = 0; i < n; ++i) {
12                cin >> arr[i];
13                ++cnt[arr[i]];
14        }
15        for (int i = 99; i >= 1; --i) {
16                cnt[i] += cnt[i + 1];
17        }
18        for (int i = n - 1; i >= 0; --i) {
19                ans[--cnt[arr[i]]] = arr[i];
20        }
21        for (int i = 0; i < n; ++i) {
22                cout << ans[i] << (i + 1 == n ? "\n" : " ");
23        }
24        return 0;
25}

Execution Example of Counting Sort

Below is a detailed walkthrough of Counting Sort (ascending) with a concrete example.

Input data: n = 8, array arr = [3, 1, 4, 1, 5, 9, 2, 6], value range is 1~9.

Step 1: Count the frequency of each value

Traverse the array; for each element arr[i], execute ++cnt[arr[i]]:

1cnt[1] = 2  (value 1 appears 2 times)
2cnt[2] = 1  (value 2 appears 1 time)
3cnt[3] = 1  (value 3 appears 1 time)
4cnt[4] = 1  (value 4 appears 1 time)
5cnt[5] = 1  (value 5 appears 1 time)
6cnt[6] = 1  (value 6 appears 1 time)
7cnt[9] = 1  (value 9 appears 1 time)

Step 2: Compute prefix sums (determine the rank upper bound for each value)

Accumulate from left to right with cnt[i] += cnt[i-1]:

1cnt[1] = 2  (2 values are <= 1)
2cnt[2] = 3  (3 values are <= 2)
3cnt[3] = 4  (4 values are <= 3)
4cnt[4] = 5  (5 values are <= 4)
5cnt[5] = 6  (6 values are <= 5)
6cnt[6] = 7  (7 values are <= 6)
7cnt[7] = 7
8cnt[8] = 7
9cnt[9] = 8  (8 values are <= 9)

Step 3: Traverse the original array from back to front, placing elements in correct positions

Process from i = 7 down to i = 0:

1i=7: arr[7]=6, cnt[6]=7, --cnt[6]=6, ans[6]=6   -> ans=[_,_,_,_,_,_,6,_]
2i=6: arr[6]=2, cnt[2]=3, --cnt[2]=2, ans[2]=2   -> ans=[_,_,2,_,_,_,6,_]
3i=5: arr[5]=9, cnt[9]=8, --cnt[9]=7, ans[7]=9   -> ans=[_,_,2,_,_,_,6,9]
4i=4: arr[4]=5, cnt[5]=6, --cnt[5]=5, ans[5]=5   -> ans=[_,_,2,_,_,5,6,9]
5i=3: arr[3]=1, cnt[1]=2, --cnt[1]=1, ans[1]=1   -> ans=[_,1,2,_,_,5,6,9]
6i=2: arr[2]=4, cnt[4]=5, --cnt[4]=4, ans[4]=4   -> ans=[_,1,2,_,4,5,6,9]
7i=1: arr[1]=1, cnt[1]=1, --cnt[1]=0, ans[0]=1   -> ans=[1,1,2,_,4,5,6,9]
8i=0: arr[0]=3, cnt[3]=4, --cnt[3]=3, ans[3]=3   -> ans=[1,1,2,3,4,5,6,9]

Final output: 1 1 2 3 4 5 6 9

Why traverse from back to front? Traversing from back to front ensures stability -- when two elements have the same value, the one that appeared later in the original array will also appear later in the sorted array, preserving their relative order.

Problem-Solving Steps with Counting Sort

When encountering a problem that calls for Counting Sort, follow these steps:

1. Check applicability: Is the value range small (e.g., 0~100)? If the range is too large, Counting Sort is not suitable
2. Determine the value range: Based on the problem constraints, determine the size of the cnt array so it covers all possible values
3. Count frequencies: Traverse the original array and count the occurrences of each value
4. Compute prefix/suffix sums: Use prefix sum for ascending order or suffix sum for descending order
5. Place elements: Traverse the original array from back to front and place each element in its correct position
6. Output the result: Print the sorted array

Common Mistakes in Counting Sort

1. cnt array too small: The cnt array must cover the entire value range. For example, if the range is 0~100, the cnt array needs at least cnt[101]
2. Forgetting to initialize arrays: The cnt and ans arrays must be initialized to 0, otherwise the counts will be incorrect
3. Wrong prefix/suffix sum direction: Ascending order uses prefix sum (accumulate left to right), descending order uses suffix sum (accumulate right to left)
4. Forward traversal when placing elements: Traversing the original array from front to back produces correct results but loses stability
5. Negative values in the data: Counting Sort handles non-negative integers by default. If the data contains negative values, an offset must be applied first (e.g., add a constant to all values to make them non-negative)

Counting Sort with Negative Numbers

Counting Sort can only handle non-negative integers by default because array indices cannot be negative. When the data range includes negative numbers, an offset is needed: add a constant to all values so the minimum becomes 0.

For example, if the data range is -50 ~ 50, the offset is 50, so -50 maps to cnt[0] and 50 maps to cnt[100].

1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[205] = {};  // Range -100~100, after offset 0~200
6int ans[100005] = {};
7const int OFFSET = 100;  // Offset to map minimum value -100 to index 0
8
9int main() {
10        int n;
11        cin >> n;
12        for (int i = 0; i < n; ++i) {
13                cin >> arr[i];
14                ++cnt[arr[i] + OFFSET];  // Add offset before counting
15        }
16        for (int i = 1; i <= 200; ++i) {
17                cnt[i] += cnt[i - 1];
18        }
19        for (int i = n - 1; i >= 0; --i) {
20                ans[--cnt[arr[i] + OFFSET]] = arr[i];  // Note: ans stores original values
21        }
22        for (int i = 0; i < n; ++i) {
23                cout << ans[i] << (i + 1 == n ? "\n" : " ");
24        }
25        return 0;
26}

Key point: The offset is only used for the cnt array index calculations. The ans array still stores the original values, so no conversion is needed during output.

Comparison with Other Sorting Algorithms

By now, we have learned several sorting algorithms. Here is a comparison of their characteristics to help you choose the right algorithm for different scenarios:

When to use Counting Sort?

• Data consists of integers with a small value range (e.g., scores 0100, ages 0150)
• The dataset size n is large, and O(n^2) sorting algorithms would time out
• Stable sorting is required

When NOT to use Counting Sort?

• Data consists of decimals or strings (Counting Sort only works with integers)
• The value range is extremely large (e.g., 0~10^9) -- the cnt array cannot be allocated
• The dataset is small, and simple O(n^2) sorting is sufficient

Complexity Analysis of Counting Sort

The complexity and characteristics of Counting Sort are as follows (where n is the dataset size and w is the value range):

• Time Complexity: O(n + w)
• Space Complexity: O(n + w)
• Stability: Stable sort

Counting Sort is best suited for sorting data where n is large and w is small, such as sorting scores, prices, and similar scenarios. When the value range is small but the dataset is large, Counting Sort is far more efficient than comparison-based sorting algorithms.

III. Homework

Programming Exercises

1. Most Frequent Lowercase Letter: L2174
2. Mode: L2175