-
Counting Sort Algorithm
-
Counting Sort Example
-
Counting Sort Algorithm Implementation
-
Counting Sort Algorithm Complexity
Counting sort is a non-comparative sorting algorithm. It sorts an array by counting occurrences of each unique element. It partially hashes the count of unique elements and then performs calculations to find the index of each element in the final, sorted array. It is quite a fast algorithm but unsuitable for large datasets. It is used as a subroutine inside radix sort.
Counting Sort Algorithm
Let us assume that we have an unsorted array A[]
containing n
elements.
Find out the maximum element max
and minimum element min
inside the array.
Initialize an array count
of length max-min+1
with all elements set to 0
.
Store the count of all elements inside the count
array by subtracting min
and using the difference as the index.
Cumulate the sum of elements inside the count
array. The count
array now holds the position of each element in the sorted array.
Starting from the end take elements from A
and do the following:
Compute elements index as count[A[i]-min]-1
and store A[i]
in output
.
decrease count[A[i]-min]
by 1
.
Store the output
elements back to original array A
.
Counting Sort Example
Suppose we have the array: (6, 3, 2, 7, 4, 5, 4, 2)
. We will sort it using the counting sort algorithm.
maxm
= 7
minm
= 2
range
= 6
count
and output
are initialized with zeros.
index |
0 |
1 |
2 |
3 |
4 |
5 |
value |
0 |
0 |
0 |
0 |
0 |
0 |
count
array after computing the count of all the elements.
index |
0 |
1 |
2 |
3 |
4 |
5 |
value |
2 |
1 |
2 |
1 |
1 |
1 |
count
array after cumulation of the sum of elements.
index |
0 |
1 |
2 |
3 |
4 |
5 |
value |
2 |
3 |
5 |
6 |
7 |
8 |
|
|
count |
1 3 5 6 7 8 |
output |
0 2 0 0 0 0 0 0 |
|
|
count |
1 3 4 6 7 8 |
output |
0 2 0 0 4 0 0 0 |
|
|
count |
1 3 4 5 7 8 |
output |
0 2 0 0 4 5 0 0 |
|
|
count |
1 3 3 5 7 8 |
output |
0 2 0 4 4 5 0 0 |
|
|
count |
1 3 3 5 7 7 |
output |
0 2 0 4 4 5 0 7 |
|
|
count |
0 3 3 5 7 7 |
output |
2 2 0 4 4 5 0 7 |
- Seventh Iteration:
A[1]=3
|
|
count |
0 2 3 5 7 7 |
output |
2 2 3 4 4 5 0 7 |
|
|
count |
0 2 3 5 6 7 |
output |
2 2 3 4 4 5 6 7 |
Finally, we store the output
array inside A
and get the sorted array - 2, 2, 3, 4, 4, 5, 6, 7
.
Counting Sort Algorithm Implementation
#include<iostream>
using namespace std;
const int N = 10;
int maxm(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
int minm(int arr[], int n) {
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
}
void countingSort(int arr[], int n) {
int min = minm(arr, n);
int max = maxm(arr, n);
int range = max - min + 1;
int count[range]={};
int output[n];
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
int main() {
int n = 7;
int arr[7] = {3, 5, 1, 1, 4, 2, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
countingSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
This implementation also works for negative numbers.
Counting Sort Algorithm Complexity
Time Complexity
Counting Sort iterates through all the n
items twice and iterates through the count
array once. So, it has a time complexity of O(n + b)
where b
is the range of input. Since b
is often small, the counting sort’s time complexity is said to be of the order of [Big Theta]: O(n)
.
The worst-case time complexity is [Big O]: O(n)
.
The best-case time complexity is [Big Omega]: O(n)
. It is the same as the worst-case time complexity.
Space Complexity
Space Complexity for the counting sort algorithm is O(n+b)
, where b
is the range of input. It comes from count
&output
arrays. Sometimes b
can be larger than n
, but if b is small, the time complexity is said to be of O(n)
.
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the
write for us page.
Binary Sort
Radix Sort