What is Counting Sort
Counting sort is a sorting technique which is based on the range of input value. It is used to sort elements in linear time. In Counting sort, we maintain an auxiliary array which drastically increases space requirement for the algorithm implementation
It works just like hashing, first, we calculate the max value in the input array, the array to be sorted. Then we count the number of occurrences of each array element from 0 to length-1 and assign it into the auxiliary array. This array is used again to retrieve the sorted version of the input array
It actually has linear time complexity but we can’t say that it’s the best algorithm because the space complexity is quite high and it is only suitable to use in a scenario where input array element range is close to the size of the array.
Counting Sort Pseudo-code
- Iterate the input array and find the maximum value present in it.
- Declare a new array of size max+1 with value 0
- Count each and every element in the array and increment its value at the corresponding index in the auxiliary array created
- Find cumulative sum is the auxiliary array we adding curr and prev frequency
- Now the cumulative value actually signifies the actual location of the element in the sorted input array
- Start iterating auxiliary array from 0 to max
- Put 0 at the corresponding index and reduce the count by 1, which will signify the second position of the element if it exists in the input array
- Now transfer array received in the above step in the actual input array
Counting Sort Algorithm
countingSort(arr, n)
maximum <- find the largest element in arr
create a count array of size maximum+1
initialise count array with all 0's
for i <- 0 to n
find the total frequency/ occurrences of each element and
store the count at ith index in count arr
for i <- 1 to maximum
find the cumulative sum by adding current(i) and prev(i-1) count and store
it in count arr itself
for j <- n down to 1
copy the element back into the input array
decrement count of each element copied by 1
Counting Sort Algorithm Dry Run
input:
| 0 | 1 | 2 | 3 | 4 |
| 2 | 1 | 1 | 4 | 2 |
First step – marking count array
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 |
After calculating all the frequency of every element
| 0 | 1 | 2 | 3 | 4 |
| 0 | 2 | 2 | 0 | 1 |
do cumulative sum
| 0 | 1 | 2 | 3 | 4 |
| 0 | 2 | 4 | 4 | 5 |
Now start iterating input array and check frequency array to map it to the output array
Iteration 1
input:
| 0 | 1 | 2 | 3 | 4 |
| 2 | 1 | 1 | 4 | 2 |
cumulative sum
| 0 | 1 | 2 | 3 | 4 |
| 0 | 2 | 3 | 4 | 5 |
Output:
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 2 | 0 |
Iteration 2
input:
| 0 | 1 | 2 | 3 | 4 |
| 2 | 1 | 1 | 4 | 2 |
cumulative sum
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 3 | 4 | 5 |
Output:
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 0 | 2 | 0 |
Iteration 3
input:
| 0 | 1 | 2 | 3 | 4 |
| 2 | 1 | 1 | 4 | 2 |
cumulative sum
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 3 | 4 | 5 |
Output:
| 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 0 | 2 | 0 |
Iteration 4
input:
| 0 | 1 | 2 | 3 | 4 |
| 2 | 1 | 1 | 4 | 2 |
cumulative sum
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 3 | 3 | 4 |
Output:
| 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 0 | 2 | 4 |
Iteration 5
input:
| 0 | 1 | 2 | 3 | 4 |
| 2 | 1 | 1 | 4 | 2 |
cumulative sum
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 2 | 3 | 4 |
Output:
| 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 2 | 4 |
Now transfer the output to the input array
Counting Sort Time Complexity
- Time is taken to find max say k
- Count array initialization will take k time
- To maintain count array again k time
- Now linear iteration of the input array to do the actual sorting
- Since all the above steps are fixed for no matter what the input array is, therefore best, average and worst time complexity will remain the same
- Best Time Complexity : O(n+k)
- Average Time Complexity : O(n+k)
- Worst Time Complexity : O(n+k)
Counting Sort Space Complexity
- Auxiliary space is required in Counting sort implementation as we have to create a count array of size max+1
- Hence space complexity is: O(max)
Counting sort in C
#include <stdio.h>
void countingSort(int arr[], int n) {
int arr1[10];
int x = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > x)
x = arr[i];
}
int count_arr[10];
for (int i = 0; i <= x; ++i) {
count_arr[i] = 0;
}
for (int i = 0; i < n; i++) {
count_arr[arr[i]]++;
}
for (int i = 1; i <= x; i++) {
count_arr[i] += count_arr[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
arr1[count_arr[arr[i]] - 1] = arr[i];
count_arr[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = arr1[i];
}
}
void display(int arr[], int n) {
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("n");
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
display(arr, n);
}
Output of the program: 1 2 2 3 3 4 8
Counting sort in Java
import java.util.Arrays;
class CountingSort {
void countSort(int arr[], int n) {
int[] arr1 = new int[n + 1];
int x = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > x)
x = arr[i];
}
int[] count_arr = new int[x + 1];
for (int i = 0; i < x; ++i) {
count_arr[i] = 0;
}
for (int i = 0; i < n; i++) {
count_arr[arr[i]]++;
}
for (int i = 1; i <= x; i++) {
count_arr[i] += count_arr[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
arr1[count_arr[arr[i]] - 1] = arr[i];
count_arr[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = arr1[i];
}
}
void display(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
public static void main(String args[]) {
int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
int n = arr.length;
CountingSort cs = new CountingSort();
cs.countSort(arr, n);
cs.display(arr);
}
}
Output of the program: 1 2 2 3 3 4 8
Counting sort in C++
#include <iostream>
using namespace std;
void countSort(int arr[], int n) {
int arr1[10];
int count_arr[10];
int x = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > x)
x = arr[i];
}
for (int i = 0; i <= x; ++i) {
count_arr[i] = 0;
}
for (int i = 0; i < n; i++) {
count_arr[arr[i]]++;
}
for (int i = 1; i <= x; i++) {
count_arr[i] += count_arr[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
arr1[count_arr[arr[i]] - 1] = arr[i];
count_arr[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = arr1[i];
}
}
void display(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]);
countSort(arr, n);
display(arr, n);
}
Output of the program: 1 2 2 3 3 4 8
Counting sort in Python
def countingSort(arr):
n = len(arr)
arr1 = [0] * n
x = [0] * 10
for i in range(0, n):
x[arr[i]] += 1
for i in range(1, 10):
x[i] += x[i - 1]
i = n - 1
while i >= 0:
arr1[x[arr[i]] - 1] = arr[i]
x[arr[i]] -= 1
i -= 1
for i in range(0, n):
arr[i] = arr1[i]
arr = [4, 2, 2, 8, 3, 3, 1]
countingSort(arr)
print(arr)
Output of the program: [1, 2, 2, 3, 3, 4, 8]
This brings us to the end of this article where we learned about heap sort. To get a free course on data structures and algorithms, click on the banner below. Also, visit the great learning academy to see all the free courses we are providing.
