Counting Sort Algorithm in Java

1. Introduction

Counting Sort is a non-comparison-based sorting algorithm that determines, for each input element, the number of elements that are less than it. It leverages this information to place each element directly into its correct position in the output array. 

The algorithm works best when the range of possible input values (i.e., the difference between the maximum and minimum values) is not significantly larger than the number of input values.

2. Implementation Steps

1. Find the maximum and minimum values in the array.

2. Create a count array of size max - min + 1 to store the count of each number.

3. Populate the count array with the number of times each number appears in the original array.

4. Modify the count array such that each element at each index stores the sum of the previous counts.

5. Output the sorted values by referencing the modified count array.

3. Implementation in Java

public class CountingSort {
    public static void sort(int[] arr) {
        int max = findMax(arr);
        int min = findMin(arr);
        int range = max - min + 1;
        // Create count array and output array
        int[] count = new int[range];
        int[] output = new int[arr.length];
        // Count occurrences of each number in the original array
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }
        // Modify count array
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        // Build the output array
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }
        // Copy output array to the original array
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
    private static int findMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
    private static int findMin(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        return min;
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Original array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        sort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Output:

Original array:
4 2 2 8 3 3 1
Sorted array:
1 2 2 3 3 4 8

Explanation:

1. The findMax and findMin helper functions are used to determine the range of input values.

2. A count array is initialized to store the frequency of each element in the original array.

3. The count array is then modified such that each element at a given position i contains the number of elements that are less than or equal to i in the original array.

4. The sorted array is constructed by referencing the count array. By doing so, each element in the original array is placed directly into its correct position in the output array.

5. The sorted values in the output array are copied back to the original array.