Counting Sort Algorithm in Java

Post Views: 36

In this Java tutorial, we are going to discuss Counting sort in Java. In the comparison based sorting the best sorting has the complexity of O(log n). To improve time complexity of sorting algorithms we are discussing linear sorting algorithm which works on some assumption and reduces the time complexity to linear.

Some of the Linear Sorting algorithms are:-

Counting sort in Java

It is not that counting sort is a comparison sort algorithm and gives O( n ) complexity for sorting. In Counting sort it is assumed that all array elements are in the range between m to k where m and k are integers. So, the time complexity of sorting is linear i.e. O ( k-m ).

The basic idea behind counting sort is to determine the number of elements less than x for each input element x and put that element x at its correct position.

A very similar post on Counting sort with a different program, – Implementation of Counting sort in Java

Algorithm

Input an array a[] in which array is in a known range k.
Take another array b[] of range k and initialize it with 0.
Store the frequency of all elements till k.
Now, print the value of all elements between lower_bound to upper_bound of array a[] on basis of its frequency.
Finally, we got the sorted array.

Code Snippet to store the frequency of all elements of array a[]

for(int i=1;i<=n;i++)
{
   b[a[i]]++;
}

Code Snippet to print the elements on basis of its frequency

for(int i=1;i<=n;i++) 
  {   
       while(b[i]>0)
    { 
         System.out.print(i+" ");
           b[i]--;
     }
}

Java code for counting sort of an array

import java.util.*;

import java.util.Scanner;

class Codespeedy

{
      public static void sort(int a[] , int n)
   
    {
        int b[] = new int[1000];
        
        for(int i=1;i<=n;i++)
             b[i]=0;
        
        for(int i=1;i<=n;i++)
       
        {
           b[a[i]]++;        
        
        }
      
      for(int i=1;i<=n;i++)
      {
             while(b[i]>0)
          
          {
            System.out.print(i+" ");
            
                 b[i]--;
          }
      }
        
    }
    
      public static void main(String[] args)
   
    {
        Scanner scan = new Scanner ( System.in);
        
            int n = scan.nextInt();
            
            int a[] = new int[1000];
            
            for(int i=1;i<=n;i++)
           
            {
                int x=scan.nextInt();
                  a[i]=x;
            }
            
            sort(a,n);
    }
}

INPUT

4

4 3 2 2

OUTPUT

2 2 3 4