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). Hence counting sort is among the fastest sorting algorithms around, in theory. It is also one of the few linear sorting algorithm or O(n) sorting algorithm. 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 future, you can mention Radix sort, bucket sort, or counting sort algorithms.  How does counting sort algorithm works? Well, counting sort creates a bucket for each value and keep a counter in each bucket. Then each time a value is encountered in the input collection,  the appropriate counter is incremented.

Because counting sort 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 count array and print them up depending upon their frequency. For example, if input array contains 0 five times then at the zeroth index of 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.

There is a large number of counting sort code on the Internet, including on university websites, that erroneously claim to be bucket sort. 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. please refer CLRS book for more details.



How to implement Counting Sorting in Java

You can follow below steps to implement 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 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.


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}



Java Program to sort Integer array using Counting Sort Algorithm

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 Solution:
 *   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]



Counting Sort FAQ

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

Is counting sort stable algorithm?
Yes, The counting sort is a stable sort i.e., 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 a good algorithm book e.g. Introduction to Algorithm by Thomas H. Cormen to learn about them.


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


Is counting sort in place?
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.


Is counting sort, a comparison based algorithm?
No, the couting 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 algorithm.


Can you use 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 e.g. short, byte or char array.

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, here 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 count array or frequency array you just go through input array and increment counter in the respective index, which serves as a key.

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

Here is a diagram which explains this beautifully:

Counting Sort in Java - Example



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

Further Learning
Algorithms and Data Structures - Part 1 and 2
Java Fundamentals, Part 1 and 2
Cracking the Coding Interview - 189 Questions and Solutions
15 Data Structure and Algorithm Questions from Interviews
Famous Data Structure and Algorithm Books
Insertion sort algorithm in Java

Thanks for reading this article. If you like this article then please share with your friends and colleagues. If you have any question or suggestion then please drop a comment and I'll try to find an answer for you. 

No comments:

Post a Comment