Java Tutorial

# 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 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");
}
}
}
```
Output:
```\$ 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
```

Java Tutorial