Counting sort algorithm Java

Sorting algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.

There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.

To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and implement them in Java.

Today we will look at counting sort.

So far, we have discussed:

• Sorting algorithms: Introduction to data sorting
• Bubble sort
• Comb sort
• Big O notation: analysis of algorithms’ time and space complexity
• Selection sort
• Insertion sort

What is counting sort

So far we have discussed algorithms that compare elements and produce a sorted output based on that comparison. Counting sort is the first non-comparison-based sorting algorithm we’re introducing.

Counting sort is an integer-stable sorting algorithm based on counting objects with different key values to determine their position in the output sequence. It should only be used in situations where the variance of the maximum and minimum key values is relatively small compared to the number of elements on the input. This algorithm is often used as an auxiliary routine in the radix sort.

Counting sort step by step

The counting sort algorithm is suitable when we have many elements with integer keys, ideally repeating from a relatively small range (max – min), then we can use this relatively efficient algorithm to sort the input elements. It works by counting the occurrences of each key and storing them in an auxiliary array. This is then transformed into an array of indices with the resulting positions of each element. It is then used to map the elements from the input vector to the output vector.

The best way to understand how the algorithm works is through a practical example in Java, which we will implement.

Counting sort advantages

• Easy to implement
• Fast and efficient when the range of k is small compared to the number of elements in the input n,
• Stable

Counting sort disadvatages

• Only works with integer keys
• Inefficient for large ranges

Counting sort time complexity

The variable k is the number of elements in the array to be counted, mathematically k = (maximum – minimum + 1). Since we iterate over the input array of elements, we get a time complexity of O(n). Iterating over the auxiliary array contributes a complexity of O(k), so the total time complexity is O(n+k).

Storing k elements in an auxiliary array in memory results in a counting sort space complexity of O(k).

Counting sort animation, visualization, gif

The counting sort visualization looks like this:

Source : https://commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

Counting sort animation can be found on this page.

Counting sort Java implementation

We will now show a simple implementation of the counting sort algorithm in Java.

CountingSort.java

package sorting;

public class CountingSort {
    private int min, max;

    public void sort(int data[])
    {
        // Don't sort if there are no elements
        if(data.length == 0)
            return;

        // Create ouput array
        int[] output = new int[data.length];

        // Find min and max value in 1 loop
        min = data[0];
        max = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] < min) {
                min = data[i];
            } else if (data[i] > max) {
                max = data[i];
            }
        }

        // Create count array
        int k = max - min + 1;
        int[] count = new int[k];
        System.out.println("min = " + min + ", max = " + max +
                ", size (n) = " + data.length + ", range (k) = " + k);

        // Count occurrences of elements
        for (int i = 0; i < data.length; i++) {
            count[data[i] - min]++;
        }
        System.out.print("Count array: ");
        printArray(count);

        // Transform counts to positions
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        System.out.print("Transformed count array: ");
        printArray(count);

        // Map the elements from input to output based on count indexes
        // Do it backwards
        for (int i = data.length - 1; i >= 0; i--) {
            output[count[data[i] - min] - 1] = data[i];
            count[data[i] - min]--;
        }

        // Copy the elements from output back to original array
        for (int i = 0; i < data.length; i++) {
            data[i] = output[i];
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

The algorithm consists of the following steps, which we will explain briefly:

Check empty array

If the array is empty, there is nothing to sort.

Finding the minimum and maximum values

Let’s find out the range of values of min and max.

Creating and initializing a counting array

The size of the count array is the difference between the maximum and minimum value plus one to cover the entire range of values.

Counting the occurrences of elements

For each element in the input array, the value at the corresponding index in the counting array is incremented by one.

Transformation to accumulated counts

Each element in the counting array is updated to the sum of all previous values, which determines the final positions of the elements in the output array.

Placement of elements in the output array

The input array is traversed backwards (to ensure stability) and elements are placed in the output array based on the values in the counting array, decrementing the counting array index by 1 after each element placement.

Copy the output back to the original array

The sorted elements from the output array are copied back to the original array.

Main.java

import sorting.CountingSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 4, 2, 4, 2, 1, 1, 1, 7, 6, 3, 5, 5 };
        CountingSort countingSort = new CountingSort();
        System.out.print("Input: ");
        countingSort.printArray(dataToSort);
        countingSort.sort(dataToSort);
        System.out.print("Sorted: ");
        countingSort.printArray(dataToSort);
    }
}

The output of this counting sort example is:

Counting sort Java code example

We have prepared the files with the above example as code that you can run directly in Java. Download the Java counting sort code here.

If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers!

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.