Counting Sort
Counting Sort Algorithm in C++ (Complete Implementation)
C++ Counting Sort Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#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;
}Original array: 4 2 2 8 3 3 1 Sorted array: 1 2 2 3 3 4 8
Understanding Counting Sort
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:
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
---
3. Understanding Counting Sort
Algorithm Concept
:
Visual Example
:
---
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];
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];
}
// Store count of each elementHow it works
:
---
5. Step-by-Step Algorithm
Step 1: Find Range
Step 2: Count Occurrences
Step 3: Calculate Positions
Step 4: Build Output
---
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)
Space Complexity
: O(n + k)
Stability
: Stable
---
8. When to Use Counting Sort
Best For
:
Not Recommended For
:
---
9. Important Considerations
Range Calculation
:
Stability
:
Index Mapping
:
---
10. return 0;
This ends the program successfully.
---
Summary
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.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for Counting Sort
This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.