Monday, 9 October 2017

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.


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]

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

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.

Related Posts