Sorting is one of the foundational tasks in programming, helping organize data efficiently so that it can be easily searched, analyzed, or processed. One interesting sorting algorithm that beginners should know is Counting Sort. Unlike comparison-based sorting methods such as bubble sort or merge sort, Counting Sort uses the frequency of elements to determine their correct position in the sorted array. This makes it extremely efficient when dealing with integers within a small range.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is particularly useful in scenarios where you have numbers that fall into a predictable range, like grades, scores, ages, or small datasets of IDs. It’s a stable sorting algorithm, which means that elements with equal values retain their original relative order. Understanding Counting Sort helps beginners see an alternative to comparison-based sorting and appreciate how clever use of counts and indices can lead to very fast sorting.
Program 1: Basic Counting Sort (Ascending Order)
This first program shows the standard Counting Sort approach. It counts occurrences of each element, calculates their positions, and builds a sorted array.
#include <iostream>
#include <vector>
using namespace std;
void countingSort(int arr[], int n) {
int maxVal = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > maxVal)
maxVal = arr[i];
vector<int> count(maxVal + 1, 0);
for (int i = 0; i < n; i++)
count[arr[i]]++;
int index = 0;
for (int i = 0; i <= maxVal; i++) {
while (count[i]-- > 0) {
arr[index++] = i;
}
}
}
int main() {
int arr[] {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}In this program, we first find the maximum value in the array to know the size of the counting array. Then we count the occurrences of each element and place them in order. This approach is straightforward and shows beginners how frequencies can replace direct comparisons in sorting.
Program 2: Counting Sort with Output Array
This version demonstrates a slightly more advanced approach that uses a separate output array. It preserves the original array and also ensures stability, which is important when sorting elements with additional associated data.
#include <iostream>
#include <vector>
using namespace std;
void countingSortStable(int arr[], int n) {
int maxVal = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > maxVal)
maxVal = arr[i];
vector<int> count(maxVal + 1, 0);
for (int i = 0; i < n; i++)
count[arr[i]]++;
for (int i = 1; i <= maxVal; i++)
count[i] += count[i - 1];
vector<int> output(n);
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
int main() {
int arr[] {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSortStable(arr, n);
cout << "Stable sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}Here, we build a cumulative count array to determine the exact position of each element in the output array. Processing the original array from end to start ensures stability, meaning elements with the same value maintain their relative order. Beginners can learn how stability can be important when sorting more complex data, like objects with multiple attributes.
Program 3: Counting Sort in Descending Order
Sometimes, we need numbers sorted from largest to smallest. This version of Counting Sort reverses the placement logic to achieve descending order.
#include <iostream>
#include <vector>
using namespace std;
void countingSortDescending(int arr[], int n) {
int maxVal = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > maxVal)
maxVal = arr[i];
vector<int> count(maxVal + 1, 0);
for (int i = 0; i < n; i++)
count[arr[i]]++;
int index = 0;
for (int i = maxVal; i >= 0; i--) {
while (count[i]-- > 0) {
arr[index++] = i;
}
}
}
int main() {
int arr[] {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSortDescending(arr, n);
cout << "Sorted array in descending order: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}By iterating from the largest value down to zero, this version sorts the array in descending order. Beginners can see how a simple change in loop direction can switch the sort order while keeping the algorithm structure intact.
Program 4: Counting Sort Handling Negative Numbers
This program sorts an array containing both negative and positive integers by shifting the range to start from zero.
#include <iostream>
#include <vector>
using namespace std;
void countingSortWithNegatives(int arr[], int n) {
// Find the minimum and maximum values
int minVal = arr[0], maxVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxVal) maxVal = arr[i];
if (arr[i] < minVal) minVal = arr[i];
}
int range = maxVal - minVal + 1;
vector<int> count(range, 0);
// Count occurrences, shifting by minVal
for (int i = 0; i < n; i++)
count[arr[i] - minVal]++;
// Reconstruct the sorted array
int index = 0;
for (int i = 0; i < range; i++) {
while (count[i]-- > 0) {
arr[index++] = i + minVal; // shift back to original value
}
}
}
int main() {
int arr[] {4, -2, 2, -8, 3, 3, -1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSortWithNegatives(arr, n);
cout << "Sorted array with negative numbers: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}In this program, we first find the minimum and maximum values to determine the range. By shifting each number with arr[i] - minVal, we ensure all numbers start from zero, allowing counting sort to work. After sorting, we shift the numbers back by adding minVal.
This approach allows Counting Sort to handle arrays containing negative numbers, keeping the algorithm simple and efficient. Beginners can see how a small adjustment—shifting values—extends the algorithm to a wider range of data.
Frequently Asked Questions (FAQ)
Here are some common questions beginners often have about Counting Sort:
Q1: What is Counting Sort?
Counting Sort is a sorting algorithm that uses the frequency of elements to place them in the correct order without direct comparisons.
Q2: Is Counting Sort stable?
Yes, it can be made stable by using an output array and cumulative counts. Stability ensures equal elements keep their original relative order.
Q3: Can Counting Sort handle negative numbers?
The standard algorithm handles non-negative integers. For negative numbers, you need to shift the values so the minimum is zero.
Q4: What is the time complexity of Counting Sort?
It is O(n + k), where n is the number of elements and k is the range of input values.
Q5: When should I use Counting Sort?
It’s best for arrays of integers with a small to moderate range, especially when stability is important or fast linear-time sorting is required.
Conclusion
Counting Sort is a simple yet powerful sorting algorithm, particularly effective for integer arrays with a limited range. In this article, we explored multiple C++ implementations: a basic ascending order version, a stable version using an output array, and a descending order version. Beginners can see how counting occurrences, using cumulative sums, and managing output arrays lead to fast and reliable sorting.
By practicing these programs, you can understand the concept of frequency-based sorting, the importance of stability, and how small changes can adapt the algorithm to different needs. Counting Sort is not only a great tool for learning, but also a practical solution for many real-world applications.
