Counting sort is different from other sorting algorithms like the bubble sort, selection sort, and mergesort. Those sorting algorithms are comparison based. In those sorting algorithms, elements are compared among them.
If the range of the elements of the array is not too big, then we can apply counting sort.
Suppose we have an array a={15, 12, 11, 12,20, 15, 16, 19, 12, 10, 12, 12, 18, 19, 14, 15, 10, 19}
All the elements are between 10 to 20. As the range is small, we can use counting sort.
We will count how many times each element occur in this array.
As elements are between 10 to 20, there are 20-10+1 unique elements. If we map 10 with 0, 11 with 1, and so on, we will need only 20-10+1 auxiliary space.
Counting sort using C
#include <stdio.h>
int main() {
int a[]={15, 12, 11, 12,20, 15, 16, 19, 12, 10, 12, 12, 18, 19, 14, 15, 10, 19};
int cnt[20-10+1]={0};
for(int i=0;i<18;i++)
{
cnt[a[i]-10]++;
}
int j=0;
for(int i=0;i<20-10+1;i++)
{
while(cnt[i])
{
cnt[i]--;
a[j++]=i+10;
}
}
for(int i=0;i<18;i++) printf("%d ", a[i]);
return 0;
}
Counting sort using c++
#include <iostream>
int main() {
int a[]={15, 12, 11, 12,20, 15, 16, 19, 12, 10, 12, 12, 18, 19, 14, 15, 10, 19};
int cnt[20-10+1]={0};
for(int i=0;i<18;i++)
{
cnt[a[i]-10]++;
}
int j=0;
for(int i=0;i<20-10+1;i++)
{
while(cnt[i])
{
cnt[i]--;
a[j++]=i+10;
}
}
for(int i=0;i<18;i++) printf("%d ", a[i]);
return 0;
}
Counting sort using JAVA
import java.util.*;
class HelloWorld {
public static void main(String[] args) {
int a[]={15, 12, 11, 12,20, 15, 16, 19, 12, 10, 12, 12, 18, 19, 14, 15, 10, 19};
int cnt[]=new int[20-10+1];
for(int i=0;i<18;i++)
{
cnt[a[i]-10]++;
}
int j=0;
for(int i=0;i<20-10+1;i++)
{
while(cnt[i]>0)
{
cnt[i]--;
a[j++]=i+10;
}
}
System.out.println(Arrays.toString(a));
}
}
Counting sort using Javascript
let a=[15, 12, 11, 12,20, 15, 16, 19, 12, 10, 12, 12, 18, 19, 14, 15, 10, 19];
let cnt=[];
for(let i=0;i<20-10+1;i++) cnt.push(0)
for(let i=0;i<18;i++)
{
cnt[a[i]-10]++;
}
let j=0;
for(let i=0;i<20-10+1;i++)
{
while(cnt[i]>0)
{
cnt[i]--;
a[j++]=i+10;
}
}
console.log(a)
Counting sort using python
a=[15, 12, 11, 12,20, 15, 16, 19, 12, 10, 12, 12, 18, 19, 14, 15, 10, 19];
cnt=[];
for i in range(20-10+1):
cnt.append(0)
for i in a:
cnt[i-10]=cnt[i-10]+1
j=0
for i in range(20-10+1):
while cnt[i]>0:
cnt[i]=cnt[i]-1
a[j]=i+10
j=j+1
print(a)