Java Counting Sort Tutorial 🎯

Welcome to our deep dive into the world of Java! Today, we're going to explore a sorting algorithm known as Counting Sort. This algorithm is easy to understand and implement, making it a great choice for beginners. Let's get started!

What is Counting Sort? 📝

Counting Sort is a sorting algorithm that works by counting the occurrences of elements in an array and then using that information to sort the array. It's particularly useful when the input data can be represented as integers within a specific range.

Why Use Counting Sort? 💡

Counting Sort is an efficient sorting algorithm, especially for data with a small range. It has a worst-case and average time complexity of O(n + k), where n is the number of elements and k is the range of the input integers. This makes it faster than other sorting algorithms like Bubble Sort or Selection Sort when dealing with large ranges.

How to Implement Counting Sort in Java 🎯

Let's break down the steps to implement Counting Sort in Java:

Initialize an array count[] to store the count of each element in the original array.
Initialize an array output[] to hold the sorted elements.
Iterate through the original array and increment the corresponding count in the count[] array.
Calculate the sum total of all counts.
Iterate through the count[] array to fill the output[] array. At each step, use the current element's count from count[] to fill the output[] array.
Return the sorted output[] array.

Here's a complete example:

java

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {17, 24, 23, 2, 6, 4, 19, 10};
        int[] output = countingSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(output));
    }

    static int[] countingSort(int[] arr) {
        int max = findMax(arr);
        int[] count = new int[max + 1];
        int[] output = new int[arr.length];

        // Step 1: Initialize count array
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }

        // Step 2: Calculate sum of counts
        int total = 0;
        for (int i = 1; i <= max; i++) {
            total += count[i];
        }

        // Step 3: Fill output array
        for (int i = arr.length - 1; i >= 0; i--) {
            output[total - count[arr[i]]] = arr[i];
            count[arr[i]]--;
        }

        return output;
    }

    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;
    }
}

Now that you've learned about Counting Sort, practice implementing it on your own and try optimizing it for different input data. Happy coding! 🎉