Counting Sort in Java

In this post, we will learn how to implement Counting Sort in java. First, we will start by understanding the Counting Sort algorithm.

• Sorting Algorithms in Java

Counting Sort Algorithm

Counting Sort Algorithm is an integer-based algorithm, non-comparison, and linear sorting algorithm. The counting sort algorithm sorts the elements in an array in a specific range. It is based on keys between the specific range.

Counting sort calculates the number of occurrences of objects and stores their key values. Then by adding the previous key elements, a new array is formed.

Before we begin, you need to have an idea on following:

• Methods in java
• for loop in java
• while loop in java

Time Complexity of Counting Sort:

• Best case:  0(n+k)
• Average case:  0(n+k)
• Worst case:  0(n+k)

---

Implementation of Counting Sort in java

import java.util.Arrays;

public class CountingSortJava
{
  public static void main(String[] args)
  {
    int[] arr = { 5, 34, 3, 2, 34, 3, 5, 2, 5, 34, 6, 2 };
    int k = 34;

    System.out.println("Array before sorting");
    System.out.println(Arrays.toString(arr));

    countingSortFn(arr, k);

    System.out.println("Array after Counting sorting: ");
    System.out.println(Arrays.toString(arr));

  }

  public static void countingSortFn(int[] input, int k)
  {
   	// creating buckets 
    int counter[] = new int[k + 1];

   	// filling buckets 
    for (int i: input)
    {
      counter[i]++;
    }

   	// sorting 
    int ndx = 0;
    for (int i = 0; i < counter.length; i++)
    {
      while (0 < counter[i])
      {
        input[ndx++] = i;
        counter[i]--;
      }
    }
  }
}

The output of Counting sort algorithm in java:

---