Java Program for Counting Sort

What is counting sort ?

Counting sort finds frequency of each array elements and array elements are sorted based on counter value of each elements.

Counting Sort Algorithm

Finds maximum element in the list of elements.

Initialize counter list with 0 for all elements range from 0 to maximum element.

Finds frequency for all array elements and updates frequency value in counter list.

Sorted array elements based on counter list.

Counting Sort Steps

Counting Sorting Time complexity

Counting sort time complexity is O(N+K), here N is the number of array elements. K is the maximum element in the array.

Counting Sort Java Program

import java.util.Scanner;

public class CountingSortTest {
	public static int max(int[] listVals){		
		int maxVal = listVals[0];
		for(int i=1; i<listVals.length;i++){
			if(maxVal<listVals[i]){
				maxVal = listVals[i];
			}
		}
		return maxVal;
	}
	public static int[] countingSort(int[] listVals){
		// finds max value in the list
		int maxVal = max(listVals);
		int[] listCounts = new int[maxVal+1];
		int[] listSortedVals = new int[listVals.length];
		for(int i=0;i<maxVal+1;i++){
			listCounts[i]=0;
		}
		// finds frequency of each array elements
		for(int i=0;i<listVals.length;i++){
			listCounts[listVals[i]] += 1;
		}
		// adds elements in sorted order based on frequency.  
		for(int i=0,j=0;i<maxVal+1;i++){
			while(listCounts[i]>0){
				listSortedVals[j]=i;
				listCounts[i] -= 1;
				j++;
			}
		}
		return listSortedVals;
	} 

	public static void main(String[] args){
	    int[] numberList, sortedList;
	    Scanner in = new Scanner(System.in); 
	    System.out.println("Counting Sort");
	    System.out.println("--------------------");
	    System.out.println("Enter numbers count: ");                   
	    int count = in.nextInt();                   
	    numberList = new int[count];
	    System.out.println("Enter numbers: "); 
	    for (int i=0;i<count;i++){
	    	numberList[i]=in.nextInt();
	    }
	    in.close();
	    sortedList = countingSort(numberList);
	    
	    System.out.println("Sorted numbers: "); 
	    for(int number : sortedList){
	    	System.out.print(number+"\t");
	    }
	}
}                                                                                                                                        

$ javac CountingSortTest.java 
$ java CountingSortTest 
Counting Sort
--------------------
Enter numbers count: 
5
Enter numbers: 
3
2
1
5
4
Sorted numbers: 
1	2	3	4	5