### Counting Sort Algorithm - The Coding Shala

In this post, we will learn what is Counting Sort Algorithm and how it works. We will write a Java program for Counting Sort.

## Counting Sort Algorithm

### Working of Counting Sort Algorithm

- Step 1. We will iterate through the input once and count the number of times each item occurs.
- Step 2. Now we modify our count array to pre-compute where each item from the input should go. This step is a little be tricky. We add the previous sum to the current element in the count array. To get more understanding see the below example.
- Step 3. Now we will use our pre-computed count array to put all the elements at the given sum index in the count array and then decrease the value in the count array by 1.

The idea is to count how many 0's we see in an array, how many 1's, and so on. There are 11 possible values in the range of 0 to 10, we will use an array with 11 counters initialized to 0.

| | | | | | | | | | |

0 1 2 3 4 5 6 7 8 9 10

Now we will build the index array means will modify the counts array so can decide where each item from the input should go.

We modify the counts' array such that each element at each index stores the sum of previous counts.

### The time complexity of Counting sort

So we can say counting sort takes O(n) time and space. So why don't we use it everywhere? The reason is Counting sort only works when the range of items in the input is known ahead of time. And the range of values is big then for counting sort requires a lot of space.

## Counting Sort Algorithm Java Program

**Java Program:**

//counting sort //the coding shala class Main{ public static void counting_sort(int[] input) { int len = input.length; //range is 0 to 10(inclusive) int[] output = new int[len]; int[] counts = new int[11]; //step 1 count the numbers of element for(int i=0;i<len;i++) { counts[input[i]]++; } //modify the count array to get index to sort the array for(int i=1; i<counts.length; i++) { counts[i] += counts[i-1]; } //now take the index from counts array //insert at index in output array //decrease the value by 1 in counts array for(int i=0; i<len; i++) { int ele = input[i]; int index = counts[ele]; output[index-1] = ele; counts[ele]--; } //insert back to original array for(int i=0; i<len;i++) { input[i] = output[i]; } } public static void main(String[] args) { int[] input = {4,8,4,2,9,9,6,2,9}; int len = input.length; counting_sort(input); for(int i=0;i<len;i++) { System.out.print(input[i]+" "); } } }

**Other Posts You May Like**

- Bubble Sort Algorithm
- Bucket Sort Algorithm
- Binary Search Algorithm
- The Big O Notation
- Find Number of Islands

## Comments

## Post a Comment