Counting Sort in Java

Counting Sort is an integer sorting algorithm. Counting Sort are unlike other sorting algorithms in that it makes certain assumptions about the data. It counts the number of objects with a distinct key value, and use arithmetic to determine the position of each key. This algorithm does not make use of comparisons to sort the values. In simplistic terms, the algorithm counts the number of occurrences of each value in order to sort it.

The initial phase of the algorithm is to start counting the number of occurrences of the values within the array and increment the value associated with the counting key. The second phase is to write out the new sorted array making use of the number of occurrences of each of the counting keys.

Algorithm Classification

The following table contains information about the analysis of the Counting Sort algorithm. It defines the worst, average and best cases in terms of time complexity and also the worst case in space complexity.

Attribute	Value
Class	Sorting Algorithm
Classification	Internal, Not In-place Algorithm
Data Structure	Array
Time Complexity: Best	Ω(n+k)
Time Complexity: Average	Θ(n+k)
Time Complexity: Worst	O(n+k)
Space Complexity: Worst	O(k)

Please use the following link for an explanation on Big-O notation and what is good, fair and bad.

Counting Sort In Java

public final class CountingSort {

    public void sort(int[] collection) {
        if (collection != null) {
            int maxValue = findMaxValue(collection);
            countingSort(collection, maxValue);
        } else {
            throw new IllegalArgumentException("Input paramenter for array to sort is null.");
        }
    }

    private void countingSort(int[] collection, int maxValue) {
        int[] countArray = countOccurrences(collection, maxValue);
        reconstructArray(collection, countArray, maxValue);
    }

    private int findMaxValue(int[] collection) {
        int highest = collection[0];
        for (int index = 1; index < collection.length; index ++) {
            if (collection[index] > highest) {
                highest = collection [index];
            }
        }
        return highest;
    }

    private int[] countOccurrences(int[] collection, int maxValue) {
        int[] tempArray = new int[maxValue + 1];
        for (int i = 0; i < collection.length; i++) {
            int key = collection[i];
            tempArray[key]++;
        }    
        return tempArray;
    }

    private void reconstructArray(int[] collection, int[] countArray, int maxValue) {
        int j = 0;
        for (int i = 0; i <= maxValue; i++) {
            while (countArray[i] > 0) {
                collection[j++] = i;
                countArray[i]--;
            }
        }
    }
}

Sample Code (GitHub)

The details of the Counting Sort class can be viewed here.

The details of the Counting Sort JUnit Test class can be viewed here.

Conclusion

The Counting Sort algorithm forms part of a larger group of sorting algorithms. Learning through experience is the reason I created this post about the implementation of the Counting Sort algorithm in Java. I have learned a lot about how others have solved the Counting Sort algorithm in other languages including different implementations in Java.

The post Counting Sort in Java appeared first on Code2Bits.