... Holy crap, this makes so much sense. You count how many of each digit there is, and then you determine each digit's starting position by counting how many cells are taken up by the digits before it!

after watching many videos, i can proudly say that i'm still confused af!!!

Huh, this makes a lot of sense actually. Very well explained.

I came for an in-depth explanation of why we do the accumulative additions and was not disappointed. Thank you!

Great explanation! keep up the good work. Love your teaching style very much. FYI - For anyone who would like a Python version of counting sort based on his explanation. def counting_sort(arr): # step 1. find max mx = max(arr) # step 2. count frequency and store counts in the 'count' array count = [0 for _ in range(mx + 1)] for item in arr: count[item] += 1 # step 3. compute the max position of each number based on # the frequency stored in the 'count' array for i in range(1, len(count)): count[i] += count[i-1] # step 4. shift values in 'count' by one to the right for c in range(len(count)-1, 0, -1): count[c] = count[c-1] count[0] = 0 # step 5. fill the result array res = [0] * len(arr) for item in arr: idx = count[item] res[idx] = item count[item] += 1 # done! return res

"Simplicity is the final achievement, It's the crowning reward of art." The Guru who thought of this?

you're actually a genius at explaining this. Thank you!

Woah, that is really cool! So simple yet so effective!

that was an awesome explanation. I have been trying to get it for a while. I don't understand why he stopped making videos. This is awesome content.

This is so easy to understand! I finally got what my prof was talking about. Thank you so much!

I was trying to figure this out for 2 hours to use this in radix sort and I after I figured this out I saw your video and then I realised that I have wasted two hours thank you for your help I can understand your video easily .thank you

Fabulous! This makes so much more sense than reading wikipedia or geeksforgeeks :) Great explanation!

after many articles and videos and this video I can say I got this. thanks man

This is the best explaination ever!! Thank you very much

I love u ~~ hahaha. Good job on explaining the time complexity. feel confused after I saw MIT open course, and your series of video solve it~

this was very simply and well explained. thank you!

Before I watched this I thought that I know how counting sort works. During the video I had no idea what the heck is going on here. After watching this I kind of know how it works. So this video made me realize that I have yet something to learn! Thanks for making videos, maybe this one wasn't really helpful but your other tutorials and videos are really awesome and inspiring!

Amazing explanation!

When you say "when we look at the second instance of number one in the array" @ 4:08 what is it that you mean. Obviously if you're iteratting over it again for every number in the rage the worst case won't be n+k so there should be no aditional iteration. Hence why you use only the right array only to map out the numbers.

Do I need to keep track of the numbers that never occur in the range?

Kudos to you sir. This video show CORRECTLY how Couting Sort works. Most videos on this topic are flat out wrong or at best missing crucial steps.

This was an extremely easy to understand explanation! Thanks a lot.

Man, you just saved my life!!

Very good , excelent teacher !!!

Wonderful explanation, thanks a lot !

do we know to skip the number 2 in part two of this algorithm because it wasn't found in the original array?

Thank you so much. This makes a lot of sense.

Very well explained. Loved the video

I'm confused still.

thank you so much it was extremely helpful!!

thank you! good explanation

So useful! Thanks

sir what about for loop i=0;arr[i] ; ++i{ outputarr[count[arr[i]-1]=arr[i] --count[arr[i]]} where count is the range array and arr is the input array thats to be sorted i

Love this video, because your explanation is clear and you're doing a stable sorting algorithm

please make video on peak finding

thank you. This makes it simple.

after counting the no of occurrence for each number in array at 0:56, isn't the data sorted ? just check the the array and print one 0, three 1, zero 2 and two 3 ? why to move to the second box for cumulative counting ?

Simple but deep meaning....

Holy moly. Didn't know it was this easy

thank you, explained so well :)

shouldn't the space complexity be O(K)?

is this the same as distribution counting sort?

can u explain why do we need to shift like that?

great explanation !

Great Explanation

what is the difference between this and bucket alogirthm ?

hm that's interesting, i found a few sources saying that the worst case space complexity should be O(k) but this is indeed O(n+k)

Genius,now i understand it!!!

For anyone who’s confused about the step where he adds up the values in the second array, you can think of it like this. Let’s call that 2nd array “arr”. Each index in “arr” represents a value in the original array. The value at arr[i] tells you the number of values that are less than or equal to that index in the original array. For example, there is only one number less than or equal to 0 in the original array, that’s 0 itself. Then, since we know that there are three 1’s in the array, this means that there are four numbers less than or equal to 1 in the array(a single zero and three 1’s). And so on and so forth. Knowing this allows you to build the third array. Since you know that there is only one number in the original array that is less than or equal to 0, then 1 has to start at index 1 in the final sorted array (arrays are zero-based usually). Similarly, since you know that there are 4 numbers in the original array that are less than or equal to 1, then 2 has to start at index 4. And this continues until you’ve filled the third array. I think he explains the final sorted array well so I’ll stop here. Hope this helps as I was really confused as to why we need the 2nd array

After we get the count of each number why bother with calculating the starting index using the addition and right shifting, why not just take a variable length array like a vector in C or a list in python and just iterate through the count array and append as many of that element to your list directly. As in for the given example append 1 zero, then append 3 ones, then append 2 threes and the return this list as output. Edit: ok I realised after watching the entire video that if maintaining the order of the elements matters then you need to calculate the index as shown.

I don't understand why you'd change the smaller count array to contain the previous values's sizes before it for the sake of insertion in to the result array. It seems like a ton of extra work. You could just iterate through the count array from left to right, and decrement the values in it like you already are, and filling the result array from left to right... waaay less confustion in that method and the same run time I'm pretty sure.

It's not stable when you go left to right in the index array. When you do that the relative order of the elements changes.

Good explanation - thank you

Hi Dojo! So would it be correct to say that Counting sort does not work for negative integers?

can't we just print the first array on top right?

tryna get into USACO bronze, and then silver this year........... let's just say I have a long way to go. Good video tho, cleared up a lot for me!

THANK YOU !!!!

whoever made that was high af

Shift it to right by one cell... Nice!

i don’t know how i got here but this looks so fun tbh

This video is good but he completely ignores the 2 which is 0 times in the array. what are we doing there? because 2 is also in the 4th position. Do we write it?

Rather than doing accumulative addition, why don't we keep inserting the element at i-th index until its count turns 0 and we move on?

Guys can someone please explain to me why the shifting step is needed, I understand the process but why can't we just build the sorted array from the info we had with the frequency array for this example in the video: can't we just build an array that have 1 zero then 3 ones then 0 twos and finally 2 threes.

best explaination

good work Sir ! can you relate this algorithm for real world problems and examples ?

How is this only O(n+k)? Don't we have to go through the array at least twice? We first go through the array to count each occurrence. Then at the end, we have to go through the array again so we know what the index of those occurrence are or else we' can move them to the new array. So it should be at least O((n*2)+k) .... no??

Count sort does not use comparisons. That is one of the big ideas here.

Actually I fully understood at min 3. Thank you!

It works within the specific cases. If the series is [1,2,100000], it will fcking slow.

Thank you

i listened to the first 30 seconds and it finally all clicked holy crap-ah-moly

If you're only working with primitive ints and extra information is unnecessary, couldn't you just iterate through the index array and for each value stick that amount of the key int into the original? So here it would see 1 0, so put 0, then 3 1's etc.

short and crisp

This is genius

My lecturer should draw those graphs. The text description is just confusing, I don't even know which is n which is k

Hi bro please let me the logic "fixing malformed date string" It is more helpful for interview.

why not just reconstruct from count?

This is sourcery, I tell you!

This is magic...

So glad it's not like my custom sorting algorithm

that's fantastic

That was good.

why memorize the indexes? Why can't you just use the occurrences found for a number to be the amount of times you insert it down the new array until the end?

Holy Crap (2). How the f*cking this counting algorithm works.

Excellent video. Though there is a way we can simplify it further. We can eliminate the step where we move all of the elements to the next index. If you traverse original array "103131" from the back, you won't need to "shift the whole array to right by one cell" Cheers!

But then if you get negative numbers, you are screwed

it took me 6 minutes and 1 second.

But what if the element has nothing to do with the index i mean lets you have array elements that are totally different from the index number what r you gnna do in that case .you've picked easy numbers 😔

I can't understand why accumulate then shift could get the start index of each digit, it likes a magic to me. I need another brain.

Amazing! I don't get it at all!

the title: "learn something in less than 6 mins" the vid: 5:59😄

wow I thought I understood this algorithm but turns out I actually do not. I still don't wtf. I know of a way simpler way of doing this shit just my way cannot allow '0's since I would skip over the 0s when placing them in final step.

I think I should give up on this sorting technique.

Take my kneel...

now imagine if there were no repeating numbers...

This is epic

*Why we need cumulative sum*?

I am sorry to say that it is not clear at all! I usually find your videos quite straightforward but this one is quite confusing indeed.

Can't understand!

I dont get it