How to get the approach of counting sort or what actually is counting sort
Counting sort algorithm
Okay, so here’s the idea. Imagine I give you the array A of length n (where n can be very large) but I guarantee you that the elements in the array are just single digits.(i.e range from 0 to 9). Now you need to sort it. How would you go for it besides the standard sorting algorithms? Here’s an idea. We know that all 0’s will come before any 1’s and all 1’s will come before any 2’s and so on. So, basically, you just store the count of each digit in the array and then first print that much number of 0’s , then all 1’s , then all 2’s. Analyzing the complexity here is O(n) since we need just one traversal of the array. This is counting sort. Now here I provided you the idea with elements in the range [0-9] but basically elements can range from [1,m]. But you need to proceed the same way.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.