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 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 the 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 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 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 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 code 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

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 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 time and space complexity of an algorithm, please see a fundamental course like Algorithms and Data Structures - Part 1 and 2 on Pluralsight.

How does Counting Sort Algorithm works


Btw, you would need a Pluralsight membership to get access this course, which cost around $29 per month or $299 annually (14% discount).

If you don't have Pluralsight membership, I encourage you to get one because it allows you to access their 5000+ online courses on all the latest topics like front-end and back-end development, machine learning, etc. It also includes interactive quizzes, exercises, and latest certification material.

Btw, even if you don't have a membership, you can access this course for free by making use of their 10-day Free Pass which allows 200 minutes of free access to all of their quality online courses.



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 the increasing order using 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 uses cases and more information on this linear time sorting algorithm, I suggest you read the classic CLRS book on Algorithms. Introduction to Algorithms

Counting Sort algorithm in Java with Example



Counting Sort FAQ

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

1. Is counting sort 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 (unstable sorting algorithm).


2. 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).


3. Is counting sort in place 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. See a good algorithm course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to learn about them


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 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 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



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 algorithm.


6. 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 like short, byte or char array.


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
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures and Algorithms Specialization - Coursera


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 integer array whose sum is equal to a given number? [solution]
  • Write a program to find 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]
  • Famous 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 integer array of 1 to 100? [solution]
  • How do you reverse an array in place in Java? [solution]
  • 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 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 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.

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.

No comments:

Post a Comment