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
- Bubble Sort Algorithm
- Bucket Sort Algorithm
- Binary Search Algorithm
- The Big O Notation
- Find Number of Islands