Counting Sort in Java

Introduction

This tutorial explains the Counting Sort Algorithm with an example list of 7 numbers. It then provides the Java implementation of Counting Sort Algorithm and explains its Big Oh complexity.

What is Counting Sort

Counting sort is a sorting algorithm which sorts a list of non-negative integers without comparing the items with each other. Instead, it counts how many times each value occurs in the list, and then writes the values back into the list in increasing order, each value as many times as it was counted.

To keep the counts, counting sort uses a second array, called the count array. The count array has one position for every value from 0 up to the largest value in the list, so the count of a value is kept at the index equal to that value. This is why counting sort works well only when the values lie in a small range, such as marks out of 100 or ages of people.

Counting Sort Working Explained

Lets understand the working of Counting Sort using an example. Lets say the list to be sorted is [4, 2, 2, 8, 3, 3, 1].
First step - finding the largest value
The list is read once to find its largest value, which is 8. The count array therefore needs 9 positions, one for each value from 0 to 8. All the counts start at 0.

Second step - counting the values
The list is read once more. For every item, the count at the index equal to the item's value is increased by 1. The first item, 4, increases the count at index 4. The next two items, both 2, increase the count at index 2 twice, and so on. When all the items have been read, the count array is [0, 1, 2, 2, 1, 0, 0, 0, 1]. I.e. the value 0 occurs 0 times, 1 occurs once, 2 occurs twice, 3 occurs twice, 4 occurs once, and 8 occurs once.

Third step - writing the values back
The count array is now read from index 0 to index 8. For every index, the index value is written into the list as many times as its count. Index 1 writes a 1, index 2 writes two 2s, index 3 writes two 3s, index 4 writes a 4, and index 8 writes an 8. The indexes with a count of 0 write nothing. The list has now become [1, 2, 2, 3, 3, 4, 8], which is the sorted list.

Counting sort of the list 4, 2, 2, 8, 3, 3, 1 - the count array has the indexes 0 to 8, and after counting it holds 0, 1, 2, 2, 1, 0, 0, 0, 1; reading the count array from index 0 to 8 and writing each index as many times as its count gives the sorted list 1, 2, 2, 3, 3, 4, 8 Note that no two items of the list were ever compared with each other. The order of the values comes from the order of the indexes in the count array.

Counting Sort Algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
public class CountingSort {
  static int intArray[] = { 4, 2, 2, 8, 3, 3, 1 };
  public static void doSort() {
    int max = intArray[0];
    for (int i = 1; i < intArray.length; i++) {
      if (intArray[i] > max) {
        max = intArray[i];
      }
    }
    int countArray[] = new int[max + 1];
    for (int i = 0; i < intArray.length; i++) {
      countArray[intArray[i]]++;
    }
    int position = 0;
    for (int value = 0; value < countArray.length; value++) {
      for (int count = 0; count < countArray[value]; count++) {
        intArray[position] = value;
        position++;
      }//inner loop ends
    }//outer loop ends
  }
  public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
      System.out.print(" " + intArray[i]);
    }
  }
  public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort();
    System.out.print("\nArray After Sorting ->");
    printArray();
  }
}
 OUTPUT of the above code
Array Before Sorting-> 4 2 2 8 3 3 1
Array After Sorting -> 1 2 2 3 3 4 8

Explanation of the code

  • The doSort() method in the above java program holds the sorting logic. It follows the 3 steps explained above.
  • The first loop finds the largest value in the list and keeps it in max.
  • The count array countArray[] is created with max + 1 positions, so that it has an index for every value from 0 to max. Java initializes all its positions to 0.
  • The second loop reads the list and increases the count at the index equal to the value of each item, using countArray[intArray[i]]++.
  • The last two loops write the values back. The loop with the counter value goes over every index of the count array. The loop with the counter count writes that value into the list as many times as it was counted. The variable position is the next position in the list to be written.
  • The main() method orchestrates the sorting.
  • The instance element intArray[] holds the list to be sorted.

Big Oh Complexity of Counting Sort Algorithm

The list of n items is read twice - once to find the largest value and once to count the values. The count array, which has k positions for a largest value of k - 1, is read once while writing the values back. There are no nested loops which depend on n alone, as the inner loop only runs as many times in total as there are items in the list. The complexity of counting sort algorithm is thus O(n + k). The count array also needs O(k) extra space.

When k is small compared to n, counting sort can be faster than sorting algorithms which compare items, such as Quick SortClick to read tutorial: Quick Sort in Java or Merge SortClick to read: Merge Sort, which need O(n log n) time. But when k is large, for example a list of just 10 numbers with a largest value of a million, the count array becomes huge and mostly empty, and counting sort is a poor choice. Radix SortClick to read: Radix Sort works on a similar idea. It sorts numbers digit by digit, and as every digit lies in the small range 0 to 9, the items can be distributed by their digits without comparing them with each other.

Summary

In this tutorial on counting sort algorithm in java we understood how the algorithm sorts without comparing items by counting the occurrences of every value, went through a step-by-step walkthrough of sorting a 7-number list, saw the java code for implementing counting sort along with its explanation, and finally understood its Big Oh complexity and when it is a good choice.