Counting Sort in java


Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times.
Basic idea of counting sort to find number of elements less than X, so X can be put to its correct position.

Steps for Counting Sort:

  • Take an array to store count of each elements. Lets say array elements contain 1 to K then initialize count array with K.
  • Now add elements of count array, so each elements store summation of its previous elements.
  • Modified count array stores position of elements in actual sorted array.
  • Iterate over array and put element in correct sequence based on modified count array and reduce the count by 1.

Java program for counting sort:

When you run above program, you will get below output:

Time Complexity= O(N)

I would suggest to try to debug the program to understand it better.

Related posts

Add Comment