#include <iostream>
#include <algorithm>
using namespace std;
void countingSort(int arr[], int n) {
int max = *max_element(arr, arr + n);
int min = *min_element(arr, arr + n);
int range = max - min + 1;
int count[range] = {0};
int output[n];
// Store count of each element
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
// Change count to position
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
// Build output array
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
// Copy output to original array
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
countingSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}Output
Original array: 4 2 2 8 3 3 1 Sorted array: 1 2 2 3 3 4 8
This program teaches you how to implement the Counting Sort algorithm in C++. Counting Sort is a non-comparative sorting algorithm that sorts integers by counting the occurrences of each value and using those counts to determine the positions of elements in the sorted output. It's extremely efficient when the range of input values is not significantly larger than the number of elements.
1. What This Program Does
The program sorts an array of integers using the Counting Sort algorithm. For example:
- Input array: [4, 2, 2, 8, 3, 3, 1]
- Output array: [1, 2, 2, 3, 3, 4, 8]
Counting Sort works by counting how many times each value appears, then placing each element in its correct position based on these counts.
2. Header Files Used
-
#include <iostream>
- Provides cout and cin for input/output operations.
-
#include <algorithm>
- Provides max_element() and min_element() functions to find range.
3. Understanding Counting Sort
Algorithm Concept:
- Count occurrences of each value
- Calculate cumulative counts (positions)
- Place elements in correct positions
- Stable sorting algorithm
Visual Example:
Array: [4, 2, 2, 8, 3, 3, 1]
Step 1: Count occurrences
- Value 1: count = 1
- Value 2: count = 2
- Value 3: count = 2
- Value 4: count = 1
- Value 8: count = 1
Step 2: Calculate positions (cumulative counts)
- Position for 1: 0
- Position for 2: 1
- Position for 3: 3
- Position for 4: 5
- Position for 8: 6
Step 3: Place elements
- Result: [1, 2, 2, 3, 3, 4, 8]
4. Function: countingSort()
void countingSort(int arr[], int n) { int max = *max_element(arr, arr + n); int min = *min_element(arr, arr + n); int range = max - min + 1;
int count[range] = {0};
int output[n];
// Store count of each element
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
// Change count to position
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
// Build output array
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
// Copy output to original array
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
How it works:
- Finds min and max to determine range
- Counts occurrences of each value
- Converts counts to positions (cumulative)
- Places elements in correct positions (right to left for stability)
5. Step-by-Step Algorithm
Step 1: Find Range
- max = 8, min = 1
- range = 8 - 1 + 1 = 8
- Count array size: 8
Step 2: Count Occurrences
- arr[i] - min: maps value to count array index
- Example: 4 - 1 = 3 → count[3]++
- Builds frequency array
Step 3: Calculate Positions
- Cumulative sum: count[i] += count[i-1]
- Each count[i] now represents starting position
- Example: count[2] = 3 means value 3 starts at position 3
Step 4: Build Output
- Process from right to left (for stability)
- Place element at position count[arr[i] - min] - 1
- Decrement count after placement
6. Understanding Count to Position Conversion
Before (counts):
count[0] = 1 (value 1 appears 1 time) count[1] = 2 (value 2 appears 2 times) count[2] = 2 (value 3 appears 2 times) count[3] = 1 (value 4 appears 1 time) count[7] = 1 (value 8 appears 1 time)
After (positions):
count[0] = 1 (value 1 at position 0) count[1] = 3 (value 2 at positions 1-2) count[2] = 5 (value 3 at positions 3-4) count[3] = 6 (value 4 at position 5) count[7] = 7 (value 8 at position 6)
7. Time and Space Complexity
Time Complexity: O(n + k)
- n: number of elements
- k: range of values (max - min + 1)
- Counting: O(n)
- Position calculation: O(k)
- Building output: O(n)
- Total: O(n + k)
Space Complexity: O(n + k)
- Output array: O(n)
- Count array: O(k)
- Total: O(n + k)
Stability: Stable
- Processing from right to left maintains relative order
- Equal elements preserve their original order
8. When to Use Counting Sort
Best For:
- Small range of integer values
- When k is not much larger than n
- When stability is required
- Non-negative integers (or with offset)
Not Recommended For:
- Large range (k >> n) - wastes space
- Floating-point numbers
- Strings or complex objects
- When range is unknown or very large
9. Important Considerations
Range Calculation:
- range = max - min + 1
- Handles negative numbers with offset (arr[i] - min)
- Count array size equals range
Stability:
- Processing from right to left (i = n-1 to 0) ensures stability
- Equal elements maintain relative order
Index Mapping:
- arr[i] - min: maps value to count array index
- Handles any range starting from min
- Example: values 100-107 → indices 0-7
10. return 0;
This ends the program successfully.
Summary
- Counting Sort counts occurrences and uses counts to determine positions.
- Time complexity: O(n + k) where k is the range of values.
- Space complexity: O(n + k) - requires count and output arrays.
- Stable algorithm - preserves relative order of equal elements.
- Efficient when range (k) is not much larger than number of elements (n).
- Works by counting, calculating positions, and placing elements.
- Understanding Counting Sort demonstrates non-comparative sorting.
- Essential subroutine for Radix Sort algorithm.
This program is fundamental for learning non-comparative sorting algorithms, understanding counting-based techniques, and preparing for Radix Sort and other advanced sorting methods in C++ programs.