Counting Sort Algorithm in Java? Example Tutorial

Hello guys, in our last article, we looked at the Radix Sort in Java and in this article, we will look at the counting sort in Java. If you are thinking how they are related then let me tell you that both are O(n) sorting algorithms. Yes, its possible to sort in O(n) or linear time. If you are wondering that you have so far only learned that best sorting algorithms are Quick Sort and Merge Sort who sorts an array in O(nLogN) time then you are in for surprise. Yes, there existing O(n) sorting algorithms which are faster than both Quicksort and Merge sort like Radix Sort, Counting Sort, and Bucket Sort but they have their limitation. They are not general purpose sorting algorithm and you can use this to sort only integers and it also depends upon how big is the data set and how many different numbers are in the data set. 

This was actually asked to me a couple of years back when I was interviewing for a big Investment bank, even after so much reading I wasn't familiar with Counting Sort and Bucket Sort and I felt embarrassed that I didn't even heard the name of these sorting algorithm, forget about explaining how they work and when to use them. 

At that time, I let it go by simply accepting the fact that I didn't know about them but as soon as interview was over I looked at both Google and Facebook to find out what are these liner time sorting algorithms, how they work and when to use them? I was actually quite excited that I learned something new from Interview. 

I have already explained how Bucket sort works and how Radix sort works in my earlier algorithms and in this one I will just explain how Counting Sort works and then we will see code example of  how to implement Counting sort in Java. 

One of the key thing to remember about these linear sorting algorithms is that they don't sort by comparing elements and that's why the are able to give performance which is better than O(NLogN) because the moment you will start comparing elements, you will lean towards logN time.  They are also known as non-comparison sorting algorithms

How Counting Sort Algorithms works in Java?

As the name suggests Counting Sort algorithm sorts an array of integer by counting how number of times a unique element appear in the array. It woks best when your array contains small positive integers, also known as keys in this case.   

Counting sort is also not a general purpose sorting algorithms and works only when the range of element is small but you can also use it to sort negative number.  The best case, average case  and worst case performance of Counting sort algorithms all same and it is O(n +k) where k is the range of non negative key value.

Since sorting algorithms are best understood by seeing sorting in action,  here is a YouTube tutorial which explains how Counting Sort works with example, you can watch this video a couple of times to understand how Counting Sort sorts elements as its not an easy one which you can grasp in just one minute, you may be but it took me a couple of times to really get this into my head.

You can watch this YouTube tutorial right here, its from CS Dojo or you can watch it on CS Dojo channel on YouTube, one of my favorite channels. 

Java Program to Implement Counting Sort Algorithm

Here is an example of doing counting sort in Java. You can use this program to sort a list of integers in constant time with time complexity of O(n) . This means it doesn't matter if you are sorting list of 10 integer or list of 10 million integer, you will not spend exponential time. That's the power of counting sort algorithm.

import java.util.Arrays;

/**
 * Java Program to sort an array of integers with Counting Sort algorithm.
 * Counting Sort is a linear time sorting algorithm, which take advantage of
 * favorable condition to sort a list of integers in O(n) time.
 *
 * @author WINDOWS 8
 */
public class CountingSort {

    public static void main(String args[]) {

        // sorting integer array using Counting Sort
        int[] random = {4, 8, 3, 2, 9, 3, 11};
        System.out.println("Unsorted random integer array : "
                               + Arrays.toString(random));

        countingsort(random, 11);
        System.out.println("Sorted integer array : "
                             + Arrays.toString(random));

        // one more example
        int[] large = {332, 44, 32, 99, 11, 119, 434, 33};
        System.out.println("Unsorted array of integers : " 
                             + Arrays.toString(large));

        countingsort(large, 434);
        System.out.println("Sorted integer array : "
                             + Arrays.toString(large));
    }

    /*
     * Sorts integer array using Counting Sort Algorithm
     * time complexity : Best Case O(n+k); Average Case O(n+k); 
     * Worst Case O(n+k),
     * where n is the size of the input array and k means the
     * values range from 0 to k.
     */
    public static void countingsort(int[] input, int k) {
        // create buckets
        int counter[] = new int[k + 1];

        // fill buckets
        for (int i : input) {
            counter[i]++;
        }

        // sort array
        int ndx = 0;
        for (int i = 0; i < counter.length; i++) {
            while (0 < counter[i]) {
                input[ndx++] = i;
                counter[i]--;
            }
        }
    }
}

Output :
Unsorted random integer array : [4, 8, 3, 2, 9, 3, 11]
Sorted integer array : [2, 3, 3, 4, 8, 9, 11]
Unsorted array of integers : [332, 44, 32, 99, 11, 119, 434, 33]
Sorted integer array : [11, 32, 33, 44, 99, 119, 332, 434]

That's all about how to implement counting sort in Java. It's one of the O(n) sorting algorithms also known as linear time sorting algorithm and fall into category of non-comparison sorting algorithm. This means you sort numbers without comparing them. 

The best case and worst case performance for this algorithm is same and they are O(n +k ) where k is the range of non-negative numbers you are sorting. While counting sort is not a general purpose algorithm like Quicksort or Merge sort, or even heap sort, its still a nice algorithm to know as you could be asked during interviews as well. 

Other Data Structure and Algorithms articles you may like

• How to check if two given Strings are Anagram in Java? (solution)
• 100+ Data Structure and Algorithms Problems (solved)
• How to convert a numeric string to an int? (solution)
• how to rotate an array in Java? (rotate array problem)
• 10 Books to learn Data Structure and Algorithms (books)
• 10 Data Structure and Algorithms course to crack coding interview (courses)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• When to use ArrayList vs LinkedList in Java? (answer)
• 101 Coding Problems and a few tips for Tech interviews (tips)
• How to count negative numbers in a sorted matrix (matrix problem)
• Top 5 Books to Learn Data Structure and Algorithms (books)
• How to reverse words in a sentence without using a library method? (solution)
• Top 5 Books for Programming and Coding Interviews (books)
• How to convert a linked list to an array in Java? (example)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
• What is the difference between LinkedList and ArrayList in Java? (answer)
• 21 String coding Problems from Technical Interviews (questions)
• 10 Free Courses to learn Data Structure and Algorithms (courses)
• How to reverse a String in place in Java? (solution)
• How to return the highest occurred character in a String? (solution)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)

Thanks for reading this article so far. If you like this Counting sort working example in Java then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are looking for some Data Structure and Algorithms courses to improve your understanding of essential data Structure and algorithms, then you should also check these DSA online training courses for Java programmers. It's a  great course to refresh data structure fundamentals for Java Programmers.