Learn Counting Sort Algorithm in LESS THAN 6 MINUTES!

Key Takeaways

here's a quick introduction to Counting sort let's just say as an example we are trying to sort this array into an ascending order and Counting St works the best when the range of numbers each value could have is very small in the array so let's just say the range of values that we could have for each item is 0 1 2 and three the first part of applying counting sort is going to be finding the starting index for each number and it's going to be clear what I mean by that in a second and the first step for doing that is going to be counting the number of occurrences for each number in the array so for this example there's only one occurrence of zero and three occurrences of one so I'm going to write down one and three and then two occurrences of three and zero occurrences of two and we can store these numbers in an array of length four in this particular case once we have these numbers the number of occurrences for each number the second step is going to be adding each number to the right of it accumulatively what I mean by that is the first number at index zero stays the same and the second number will be 1 + 3 = 4 and the third number will be 4 + 0 which is equal to 4 and the force number at the index three will be 4 + 2 which is equal to 6 after that step we have the numbers 1 4 4 6 for the numbers 0 1 2 and three the next step is going to be shifting this whole array to the right by one cell and we're going to do that by looking at this array from right to left we're going to first start with the last index which is index three in this particular case and the value there should be the value that's currently in index 2 so we're going to put four at index 3 and we're going to do the same thing for index 2 the value here should be what's in index one currently so it should also be four and at index one we're going to put one at index zero we're going to put zero and these numbers 01 44 are actually the starting indexes for the range of numbers we have in this particular case0 1 two and three and here's one way to think about it if you look at the number three or the index three the corresponding number the corresponding starting index is four and that's because when we sort this array the number three will start at the index four another way to think about it is that there are four items that should appear before the number three in the SED array and that should be obvious if you just look at the first array that we constructed there is one occurrence of zero three occurrences of one and Zer occurrences of two so adding them up there are four items that should appear before the number three and that's why the starting index for the number three is four once we have the starting index for each number the rest is relatively easy we're going to first initialize a new array that's the same length as the original array so length six in this particular case and then we're going to iterate it through the original array 1 by one when we are looking at the first element of this array which is one we're going to check what the starting index should be for this number from the array that we constructed we see that the starting index is one so we're going to put this number into index one of the new array and then we're going to increment our starting index by one and it becomes two and this is so that when we look at the second instance of the number one we'll know that it should go to the index two instead of one and then we're going to increment it again we'll do the same thing for each number of this array from left to right until we get to the last number in the original array now you might have noticed that this process makes counting sort a stable sorting algorithm what that means is that of course if you look at different instances of the same value for example the number one the order in which they appear in the new sorted array is exactly the same as the order in which they appear in the original array this wouldn't matter if they were just number one but if they represented underlying meanings to them for example if there were ages of people three different people let's say Emily Tom and George then we might care if they appear in the same order or in a different order in the sorted array as the original unsorted array now let's quickly go through a few important properties of counting sort first of all as I mentioned it's a stable sorting algorithm and the time complexity for this algorithm is Big of n plus K where n is the number of items that we have in the original array and K is the range of numbers that we could have for each item in the array and finally the auxiliary space complexity is bigger of n plus k for counting sort because we need to create an entirely new array with length n the same size as the original array as well as an array of length K to keep track of the starting index for each number