Counting Sort in Java

Counting Sort in Java is a sorting algorithm that counts the frequency of each element and then sorts the input array in increasing order. It is efficient for sorting integers or other values with a small range.

Example:
1. Let’s say we have an array of numbers, like {4, 1, 3, 4, 2, 1, 0, 3}, that we want to sort using Counting Sort.
2. First, we find the smallest and largest numbers in the array. In this case, the smallest number is 0 and the largest number is 4.
3. Next, we create a new array called the “count” array. Its size is equal to the range of the input values (i.e., the difference between the largest and smallest numbers, plus one). In this case, the range is 5, so the count array has a size of 5.
4. We go through the input array and, for each number, we add 1 to the corresponding index in the count array. For example, when we come across the number 4, we add 1 to the count array at index 4.
5. We modify the count array by adding the previous count to the current count at each index.
6. We iterate through the input array again, and for each element, we use the count array to determine the sorted position of the element in the output array.
7. We copy the sorted elements from the output array back into the input array. Now the input array is sorted in ascending order: {0, 1, 1, 2, 3, 3, 4, 4}.

Write a Java Program to Implement Counting Sort algorithm.

The program first prompts the user to enter the number of integer elements to be sorted. Then it reads in the integer values entered by the user, and calls the Counting Sort function to sort the array.

Pseudocode for the Counting Sort Algorithm:

countingSort(array):
    max <- findMax(array)
    countArray <- new int[max+1]
    for i <- 0 to size - 1
        countArray[array[i]]++
    for i <- 1 to max
        countArray[i] += countArray[i-1]
    sortedArray <- new int[size]
    for i <- size - 1 down to 0
        sortedArray[--countArray[array[i]]] = array[i]
    for i <- 0 to size - 1
        array[i] <- sortedArray[i]

Here is the source code of the Java program to implement Counting Sort Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 ** Java Program to Implement Counting Sort
 **/
 
import java.util.Scanner;
 
/** Class CountingSort **/
public class CountingSort 
{
    private static final int MAX_RANGE = 1000000;
    /** Counting Sort function **/
    public static void sort( int[] arr )
    {
        int N = arr.length;
        if (N == 0)
            return;
        /** find max and min values **/
        int max = arr[0], min = arr[0];
        for (int i = 1; i < N; i++)
        {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
        int range = max - min + 1;
 
        /** check if range is small enough for count array **/
        /** else it might give out of memory exception while allocating memory for array **/
        if (range > MAX_RANGE)
        {
            System.out.println("\nError : Range too large for sort");
            return;
        }
 
        int[] count = new int[range];
        /** make count/frequency array for each element **/
        for (int i = 0; i < N; i++)
            count[arr[i] - min]++;
        /** modify count so that positions in final array is obtained **/
        for (int i = 1; i < range; i++)
            count[i] += count[i - 1];
        /** modify original array **/
        int j = 0;
        for (int i = 0; i < range; i++)
            while (j < count[i])
                arr[j++] = i + min;
    }    
    /** Main method **/
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner( System.in );        
        System.out.println("Counting Sort Test\n");
        int n, i;
        /** Accept number of elements **/
        System.out.println("Enter number of integer elements");
        n = scan.nextInt();
        /** Create integer array on n elements **/
        int arr[] = new int[ n ];
        /** Accept elements **/
        System.out.println("\nEnter "+ n +" integer elements");
        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        /** Call method sort **/
        sort(arr);
        /** Print sorted Array **/
        System.out.println("\nElements after sorting ");        
        for (i = 0; i < n; i++)
            System.out.print(arr[i]+" ");            
        System.out.println();                     
    }    
}

1. The program takes an array of integers as input and checks if the array is empty.
2. It finds the maximum and minimum values in the array and calculates the range of the array.
3. If the range of the array is greater than the maximum range defined in the program, it displays an error message and returns from the method.
4. It creates a count array of size equal to the range of the array.
5. The program loops through each element in the input array and updates the count array with the frequency of each element.
6. It modifies the count array to get the actual position of each element in the sorted array.
7. The program then modifies the original array with the sorted elements by iterating through the count array.
8. Finally, the program prints the sorted array.

Time Complexity: O(n+k)
The time complexity of Counting Sort is O(n+k), where n is the number of elements to be sorted and k is the range of the input data.

Space Complexity: O(k)
The space complexity of Counting Sort is O(k), where k is the range of the input data. This is because Counting Sort uses an auxiliary array of size k to store the frequency counts of the input elements.

Enter number of integer elements
20
 
Enter 20 integer elements
54 67 13 24 76 37 97 10 67 24 6 28 5 19 63 1 71 83 97 24
 
Elements after sorting
1 5 6 10 13 19 24 24 24 28 37 54 63 67 67 71 76 83 97 97

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.