Counting Sort Algorithm is an efficient sorting algorithm that can be used for sorting elements within a specific range. This sorting technique is based on the frequency/count of each element to be sorted and works using the following algorithm-
Step 1: Consider an input array A having n elements in the range of 0 to k, where n and k are positive integer numbers. These n elements have to be sorted in ascending order using the counting sort technique. Also note that A[] can have distinct or duplicate elements
Step 2: The count/frequency of each distinct element in A is computed and stored in another array, say count, of size k+1. Let u be an element in A such that its frequency is stored at count[u].
Step 3: Update the count array so that element at each index, say i, is equal to -
Step 4: The updated count array gives the index of each element of array A in the sorted sequence. Assume that the sorted sequence is stored in an output array, say B, of size n.
Step 5: Add each element from input array A to B as follows:
t = A[i]v = (count[t]-1).Repeat steps (a) to (d) till i = n-1
Step 6: Display B since this is the sorted array
Let us trace the above algorithm using an example:
Consider the following input array A to be sorted. All the elements are in range 0 to 9
A[]= {1, 3, 2, 8, 5, 1, 5, 1, 2, 7}Step 1: Initialize an auxiliary array, say count and store the frequency of every distinct element. Size of count is 10 (k+1, such that range of elements in A is 0 to k)
Figure 1: count array
Step 2: Using the formula, updated count array is -
Figure 2: Formula for updating count array
Figure 3 : Updated count array
Step 3: Add elements of array A to resultant array B using the following steps:
Figure 4: For i=0
Figure 5: For i=1
Figure 6: For i=2
Figure 7: For i=3
Figure 8: For i=4
Figure 9: For i=5
Figure 10: For i=6
Figure 11: For i=7
Figure 12: For i=8
Figure 13: For i=9
Thus, array B has the sorted list of elements.
Below we have a simple program in C++ implementing the counting sort algorithm:
#include<iostream>
using namespace std;
int k=0; // for storing the maximum element of input array
/* Method to sort the array */
void sort_func(int A[],int B[],int n)
{
int count[k+1],t;
for(int i=0;i<=k;i++)
{
//Initialize array count
count[i] = 0;
}
for(int i=0;i<n;i++)
{
// count the occurrence of elements u of A
// & increment count[u] where u=A[i]
t = A[i];
count[t]++;
}
for(int i=1;i<=k;i++)
{
// Updating elements of count array
count[i] = count[i]+count[i-1];
}
for(int i=0;i<n;i++)
{
// Add elements of array A to array B
t = A[i];
B[count[t]] = t;
// Decrement the count value by 1
count[t]=count[t]-1;
}
}
int main()
{
int n;
cout<<"Enter the size of the array :";
cin>>n;
// A is the input array and will store elements entered by the user
// B is the output array having the sorted elements
int A[n],B[n];
cout<<"Enter the array elements: ";
for(int i=0;i<n;i++)
{
cin>>A[i];
if(A[i]>k)
{
// k will have the maximum element of A[]
k = A[i];
}
}
sort_func(A,B,n);
// Printing the elements of array B
for(int i=1;i<=n;i++)
{
cout<<B[i]<<" ";
}
cout<<"\n";
return 0;
}
The input array is the same as that used in the example:
Figure 14: Output of Program
Note: The algorithm can be mapped to any programming language as per the requirement.
For scanning the input array elements, the loop iterates n times, thus taking O(n) running time. The sorted array B[] also gets computed in n iterations, thus requiring O(n) running time. The count array also uses k iterations, thus has a running time of O(k). Thus the total running time for counting sort algorithm is O(n+k).
Key Points:
Note: For a sorting algorithm to be stable, the order of elements with equal keys (values) in the sorted array should be the same as that of the input array.
