Counting Sort Implementation in Java

January 30, 2024

Counting Sort Implementation in Java

Overview

Counting Sort is a non-comparison-based sorting algorithm that efficiently sorts integers within a specified range. Unlike traditional comparison-based sorting algorithms like Quicksort or Merge Sort, Counting Sort Implementation in Java exploits the specific characteristics of the input elements to achieve linear time complexity.

Here’s a brief overview of how Counting Sort works:

Counting Occurrences: The algorithm begins by counting the number of occurrences of each unique element in the input array.
Creating a Counting Array: Based on the counts, it creates an auxiliary array, often called the “counting array,” to store the cumulative count of elements up to each unique value.
Cumulative Counting Array: The counting array is then modified to represent the cumulative count of elements. This step helps determine the correct position of each element in the sorted array.
Sorted Array Construction: Using the information from the counting array, a sorted array is constructed by placing elements in their correct positions based on their cumulative counts.
Copying Back to Original Array: Finally, the sorted array is copied back to the original array, completing the sorting process.

Counting Sort is particularly efficient when the range of possible values in the input array is small compared to the number of elements. Its linear time complexity, O(n + k), where n is the number of elements and k is the range, makes it well-suited for certain scenarios, such as sorting integers within a limited range.

Java Implementation

Counting Sort operates by counting the number of occurrences of each element in the input array and using that information to construct a sorted array. It is especially efficient when dealing with a relatively small range of integer values.

Java Program – Counting Sort

import java.util.Arrays;

public class CountingSort {

    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};

        System.out.println("Original Array: " + Arrays.toString(array));

        // Call the sort method to perform Counting Sort
        sort(array);

        System.out.println("Sorted Array: " + Arrays.toString(array));
    }

    public static void sort(int[] array) {
        int n = array.length;

        // Find the maximum element to determine the counting array size
        int max = Arrays.stream(array).max().orElse(0);

        // Create a counting array to store the count of each element
        int[] count = new int[max + 1];

        // Populate the counting array with element counts
        for (int i : array) {
            count[i]++;
        }

        // Update the counting array to represent the cumulative count
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }

        // Create the sorted array based on the counting array information
        int[] sortedArray = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            sortedArray[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }

        // Copy the sorted array back to the original array
        System.arraycopy(sortedArray, 0, array, 0, n);
    }
}

Understanding the Logic

Counting Array:

Create a counting array to store the count of each element.
Populate the counting array with the occurrences of each element in the input array.

Cumulative Count:

Update the counting array to represent the cumulative count of elements.
This step helps determine the correct positions of elements in the sorted array.

Sorted Array Construction:

Create a sorted array based on the counting array information.
Populate the sorted array by decrementing the count for each element.

Original Array Update:

Copy the sorted array back to the original array, completing the sorting process.

Example Usage

Consider an example array: {4, 2, 2, 8, 3, 3, 1}.

Counting Array:

The counting array would represent the occurrences of each element: {1, 2, 2, 0, 1, 0, 0, 1}.

Cumulative Count:

After updating, the counting array becomes {1, 3, 5, 5, 6, 6, 6, 7}.

Sorted Array:

The sorted array is constructed using the counting array information: {1, 2, 2, 3, 3, 4, 8}.

Output:

Output – Counting Sort

Original Array: [4, 2, 2, 8, 3, 3, 1]
Sorted Array: [1, 2, 2, 3, 3, 4, 8]

Complexity:

Complexity	Best Case	Average Case	Worst Case
Time Complexity	O(n + k)	O(n + k)	O(n + k)
Space Complexity	O(k)	O(k)	O(k)

Conclusion

Counting Sort is a powerful algorithm for sorting integers within a specific range efficiently. Understanding its implementation in Java provides valuable insights into its application and efficiency.

Latest Posts: