Counting Sort in Java - Example

The Counting sort algorithm, like Radix sort and Bucket sort, is an integer-based algorithm (i.e. the values of the input array are assumed to be integers), non-comparison, and linear sorting algorithm. Hence counting sort is among the fastest sorting algorithms around, in theory. It is also one of the few linear sorting algorithms or O(n) sorting algorithms. It's quite common in Java interviews nowadays to ask, whether do you know any O(n) sorting algorithm or not. If you face this question in the future, you can mention Radix sort, Bucket sort, or Counting sort algorithms.

How does the counting sort algorithm works? Well, counting sort creates a bucket for each value and keeps a counter in each bucket. Then each time a value is encountered in the input collection,  the appropriate counter is incremented.

Because the Counting sort algorithm creates a bucket for each value, an imposing restriction is that the maximum value in the input array is known beforehand. Once every value is inserted into the bucket, you just go through the count array and print them up depending upon their frequency.

For example, if the input array contains 0 (zero) five times then at the zeroth index of the count array you would have 5. Now, you can print zero 5 times before printing 1 depending upon its count. This way, you get a sorted array.

Btw, there is a large number of counting sort algorithm implementation codes on the Internet, including on university websites, that erroneously claim to be bucket sort.

There is a key difference between Bucket Sort and Counting sort, for example, Bucket sort uses a hash function to distribute values; counting sort, on the other hand, creates a counter for each value hence it is called Counting Sort algorithm. You can further check a comprehensive course like Data Structures and Algorithms: Deep Dive Using Java to learn more about it.

How to implement Counting Sorting in Java? Example

You can follow the below steps to implement the counting sort algorithm in Java:

1. Since the values range from 0 to k, create k+1  buckets. For example, if your array contains 0 to 10 then create 11 buckets for storing the frequency of each number. This array is also called a frequency array or count array.

2. To fill the buckets, iterate through the input array, and each time a value appears, increment the counter in its bucket.

3. Now fill the input array with the compressed data in the buckets. Each bucket's key represents a value in the array. So for each bucket, from smallest key to largest, add the index of the bucket to the input array and decrease the counter in the said bucket by one; until the counter is zero.

Time Complexity of the Counting Sort is O(n+k) in the best case, average case and worst case, where n is the size of the input array and k is the values ranging from 0 to k. If you want to learn more about how to calculate the time and space complexity of an algorithm, please see a fundamental course like Algorithms and Data Structures - Part 1 and 2 on Pluralsight.

Java Program to sort Integer array using Counting Sort Algorithm

Problem Statement:
You have given an unordered list of repeated integers, write a Java program to arrange them in ascending order.

Sample Input: {60, 40, 30, 20, 10, 40, 30, 60, 60, 20, 40, 30, 40}
Sample Output: {10, 20, 20, 30, 30, 30, 40, 40, 40, 40, 60, 60, 60}

import java.util.Arrays;

/*
 * Java Program sort an integer array using counting sort algorithm.
 * input: [60, 40, 30, 20, 10, 40, 30, 60, 60, 20, 40, 30, 40]
 * output: [10, 20, 20, 30, 30, 30, 40, 40, 40, 40, 60, 60, 60]
 * 
 * Time Complexity of Counting Sort Algorithm:
 *   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 class CountiSorter{

  public static void main(String[] args) {

    System.out.println("Counting sort in Java");
    int[] input = { 60, 40, 30, 20, 10, 40, 30, 60, 60, 20, 40, 30, 40 };
    int k = 60;

    System.out.println("integer array before sorting");
    System.out.println(Arrays.toString(input));

    // sorting array using Counting Sort Algorithm
    countingSort(input, k);

    System.out.println("integer array after sorting using counting sort 
                           algorithm");
    System.out.println(Arrays.toString(input));

  }

  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
Counting sort in Java
integer array before sorting
[60, 40, 30, 20, 10, 40, 30, 60, 60, 20, 40, 30, 40]
integer array after sorting using counting sort algorithm
[10, 20, 20, 30, 30, 30, 40, 40, 40, 40, 60, 60, 60]

You can see that our final array is now sorted in increasing order using the Counting sort algorithm. This is very useful if you have an integer array where values are not in a relatively small range. If you are interested in some practical use cases and more information on this linear time sorting algorithm, I suggest you read the classic CLRS book on Algorithms, also known as Introduction to Algorithms

Counting Sort FAQ

Here is some of the frequently asked question about Counting sort algorithm on interviews:

1. Is counting sort a stable algorithm?
Yes, The counting sort is a stable sort like multiple keys with the same value are placed in the sorted array in the same order that they appear in the original input array. See here to learn more about the difference between stable and unstable sorting algorithms like Mergesort (a stable sorting algorithm)  and Quicksort (an unstable sorting algorithm).


2. When do you use the counting sort algorithm?
In practice, we usually use the counting sort algorithm when having k = O(n), in which case the running time is O(n).


3. Is counting sort in place the Algorithm?
It is possible to modify the counting sort algorithm so that it places the numbers into sorted order within the same array that was given to it as the input, using only the count array as auxiliary storage; however, the modified in-place version of counting sort is not stable. 

If you are preparing for coding interviews, I also suggest you check out an interactive algorithm course like Data Structures in Java: An Interview Refresher, an interactive course on the Educative platform to refresh essential Data structure for interviews, which allows you to practice data structure and algorithms problems right in your browser. 

4. How does counting sort works?
As I said before, it first creates a count or frequency array, where each index represents the value in the input array. Hence you need a count array of k+1 to sort values in the range 0 to k, where k is the maximum value in the array. So, in order to sort an array of 1 to 100, you need an array of size 101.

After creating a count array or frequency array you just go through the input array and increment counter in the respective index, which serves as a key.

For example, if 23 appears 3 times in the input array then index 23 will contain 3. Once you create a frequency array, just go through it and print the number as many times as they appear in the count array. You are done, the integer array is sorted now.

Here is a diagram that explains this beautifully:

5. Is counting sort, a comparison-based algorithm?
No, the counting sort is not a comparison-based algorithm. It's actually a non-comparison sorting algorithm. See here to learn more about the difference between comparison and non-comparison-based sorting algorithms.


6. Can you use a counting sort to sort an array of String?
No, counting sort is an integer-based sorting algorithm, it can only sort an integer array or number array, like short, byte, or char array.


That's all about the Counting sort in Java. This is one of the useful O(n) sorting algorithms for sorting integer arrays. the linear sorting algorithm is a useful concept to remember, they are very popular nowadays in interviews. A couple of other linear sorting algorithms are Bucket sort and Radix sort. Just remember that you can only sort integer arrays using the counting sort algorithm and you need to know the maximum value in the input array beforehand.



Other Coding Problems to Practice
If you are interested in solving more Array-based algorithm problems then here is the list of some of the frequently asked coding problems from interviews:

• Insertion sort algorithm in Java (algorithm)
• How to find all pairs on an integer array whose sum is equal to a given number? [solution]
• Write a program to find the top two numbers from an integer array? [solution]
• 30+ Array-based Coding Problems from Interviews (questions)
• How to find the largest and smallest number from a given array in Java? [solution]
• Best Data Structure and Algorithm Books (books)
• 10 Free Data Structure and Algorithms Courses for Programmers [courses]
• How do you remove duplicates from an array in place? [solution]
• Write a program to find the missing number in an integer array of 1 to 100? [solution]
• How do you reverse an array in place in Java? [solution]
• 7 Best courses to learn Data Structure and Algorithms (courses)
• How to find the maximum and minimum number in an unsorted array? [solution]
• How to check if an array contains a number in Java? [solution]
• 10 Algorithms courses to Crack Coding Interviews [courses]
• How to sort an array in place using the QuickSort algorithm? [solution]
• How do you print all duplicate elements from the array in Java? [solution]
• 50+ Data Structure and Algorithms Coding Problems from Interviews (questions)
• 10 Algorithms Books Every Programmer should read [books]

Thanks for reading this article. If you like this example of Counting Sort in Java then please share it with your friends and colleagues. If you have any questions or suggestions then please drop a comment and I'll try to find an answer for you.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.