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 the following sorting algorithms:

• Sorting algorithms: an introduction to data sorting,
• Bubble sort,
• Comb sort,
• Big O notation: analyzing the complexity of algorithms,
• Selection sort – sorting by selection,
• Insertion sort – sorting by insertion.

What is counting sort

So far, we have focused on algorithms that compare elements with each other to produce a sorted output. Today, we will introduce the first algorithm that does not use comparison as its basis.

Counting sort is an integer-based stable sorting algorithm that relies on counting objects with distinct key values, from which the position in the output sequence is determined. It is suitable for use only in situations where the range between the maximum and minimum key values is relatively small compared to the number of elements in the input. This algorithm is often used as a helper routine in radix sort.

Counting sort algorithm – working principle

Counting sort algorithm is suitable if we have many elements with integer keys that ideally repeat from a relatively small range (max – min), then we can apply this relatively efficient algorithm to sort the input elements.It works on the principle of counting the occurrences of each key, which it stores in an auxiliary array. This is then transformed into an array of indices with the resulting positions of the individual elements. It is then used to map the elements from the input vector to the output vector.

The best way to understand the working principle of the algorithm is by a practical example in Java, which we will implement.

Counting sort advantages – is it stable?

• Easy to implement,
• fast and efficient if the range of kissmall compared to the number of elements in the input n,
• stable.

Disadvantages of the Counting sort algorithm – time and space complexity

• Only works for keys with integer numbers,
• inefficient for large scale

Counting sort time intensity

The variable k is the number of elements of the counting auxiliary array, 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 to O(k) complexity, so the total time complexity is O(n+k) in total.
Storing k elements in the auxiliary array in memory results in a spatial complexity of O(k).

Counting sort animation, visualization, gif

A visualisation of Counting sort looks like this:

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

Animation of the Counting sort algorithm can be found for example on this page.

Counting sort Java implementation, simulation

Now we will 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 briefly explain:

Check empty field

If the field 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 field 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 field, the value at the corresponding index in the counting field 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 field

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 field

The sorted elements from the output field are copied back to the original field. 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 example is:

Counting sort – Java code example

We have prepared the files with the above example in the form of code that you can run directly in Java. Download the Java Counting Sort code. 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.