Counting Sort Algorithm

Counting sort is a sorting algorithm that operates by counting the number of occurrences of each value in an input array. It requires that each element in the input array be an integer within a specific range.

The key idea behind counting sort is to determine, for each input element, the number of elements that are less than it. This information can be used to place each element directly into its correct sorted position without having to compare it to other elements.

Here’s how the counting sort algorithm works:

1. Find the maximum element in the input array and create a count array of size max+1 filled with zeros.
2. Traverse through the input array and increment the count of each value in the count array.
3. Modify the count array such that each element at index i stores the sum of previous counts. This step ensures that the sorted output will maintain the relative order of equal elements.
4. Create a sorted array of the same size as the input array.
5. Traverse through the input array from right to left and use the count array to place each element in its correct sorted position in the output array. Decrement the count of each element after placing it in the output array to handle duplicates.

The counting sort has a time complexity of O(n+k), where n is the size of the input array and k is the range of values. This makes it an efficient sorting algorithm when the range of the input values is not significantly larger than the size of the input array.

Example of Counting Sort

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;
}

This is a C program that sorts an array of integers in ascending order using counting sort. Here’s how it works:

• The array a contains 18 integers.
• The array cnt is created to keep track of the frequency of each integer in the range [10,20]. This is done by initializing cnt with all zeros.
• The first loop iterates through the array a and increments the count of each integer in cnt.
• The second loop iterates through the range [10,20] and repeatedly adds the current integer to the output array a as many times as its count appears in cnt. The variable j keeps track of the next empty index in a.
• Finally, the sorted array is printed out.

Note that this implementation assumes that all integers in the input array fall within the range [10,20]. If this is not the case, the size of cnt should be adjusted accordingly.

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;
}

The explanation same as the C programming above.

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));
    }
}

This is a Java program that performs the same counting sort algorithm as the C program you shared earlier. Here’s how it works:

• The main method initializes an array containing 18 integers and creates a corresponding array cnt to keep track of their frequency. Note that in Java, arrays are initialized with the new keyword and the size is specified inside square brackets.
• The first loop iterates through the array a and increments the count of each integer in cnt.
• The second loop iterates through the range [10,20] and repeatedly adds the current integer to the output array a as many times as its count appears in cnt. The variable j keeps track of the next empty index in a.
• Finally, the sorted array is printed out using the Arrays.toString method.

Like the C program, this implementation assumes that all integers in the input array a fall within the range [10,20]. If this is not the case, the size of cnt should be adjusted accordingly.

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)

This is a JavaScript program that sorts an array of integers using the counting sort algorithm. The array is initialized with 18 integers in random order. The program creates an array ‘cnt’ with length 11 (20-10+1), which will be used to count the occurrence of each integer in the range of 10 to 20.

Then the program iterates over the elements of the input array ‘a’ and increments the count of the corresponding integer in the ‘cnt’ array. After counting all the integers, the program uses two nested loops to traverse the ‘cnt’ array and update the ‘a’ array with the sorted values.

The outer loop iterates over the indices of the ‘cnt’ array, which corresponds to the integers in the range of 10 to 20. The inner loop traverses the ‘cnt’ array from the current index and decrements the count of the corresponding integer until it reaches 0. For each occurrence of an integer, the program updates the ‘a’ array with the sorted values.

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)

This is a Python program that performs the same counting sort algorithm as the earlier C and Java programs. Here’s how it works:

• The input array containing 18 integers is defined.
• An empty list cnt is created to keep track of the frequency of each integer in the range [10,20]. This is done by initializing cnt with zeros using a for loop and the append method.
• The first loop iterates through the array a and increments the count of each integer in cnt.
• The second loop iterates through the range [10,20] and repeatedly adds the current integer to the output array a as many times as its count appears in cnt. The variable j keeps track of the next empty index in a.
• Finally, the sorted list is printed out using the print function.

Like the previous implementations, this implementation assumes that all integers in the input array a fall within the range [10,20]. If this is not the case, the size of cnt should be adjusted accordingly.