... 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!
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
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!
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
You could initially add a certain numbers to all the values so that the smallest is at 0. Because you are adding a constant this will make no difference in the sorted output
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??
In big O notation, only the relative relationship matters. Even though it is 2n, it is always 2n no matter what you put in. That means it can basically be factored out or ignored. Think of f(), which has a runtime of 1, and g which has a run time of 3. Even though g takes longer, they are both O(1) because it is only the relative change in the run time with respect to n. If it take 2n second to to run, what if I redefine 1 second to be twice as long? Then it only takes n seconds, which is O(n). As you can see, when you just look at the relationship they are the same. It's kind of like how when you take the derivative of a function, any constant terms are removed. Even though x^2 + 3 is 3 more than x^2, we are only looking at the change amount of change which is the same for both.
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 ?
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.
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.
I know this probably isn't helpful now, but the reason is that this way lets you copy the elements from the original array. If you were just sorting integers, then it would be faster to just count them then generate the right number of each number from 0 to n. But if the list is actually a list of objects and the integers are just one property you are sorting by, then doing it this way lets you copy the objects into the right place. For example, in radix sort you need to run a counting sort on a multi digit, but with just a single digit of the number being sorted. The counting sort needs to retain the rest of the digits in the number, so you need to do it this way. There are other ways of doing that as well, but this way also maintains the relative order of the elements which is also needed for radix sort. If you don't need either of those properties, then the algorithm can be simplified accordingly.
I didn't understand from 4:11. I understood how to find the index of the first item of the initial array in the new array based on the constructed array, but I did not understand the part about incrementing the value by 1(around 4:11).
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?
I think you should skip a number if the next number has the same starting index. In the video 2 and 3 had the same starting index because 2 did not take up any indexes. Edit: After actually implementing the algo, I realized that this issue takes care of itself. The final step of the sort is to iterate through the original array and place each number in the OG array at it's respective starting index in the sorted array, then update the starting index for that number. Since 2 never existed, we will never find a 2 in the original array, and thus it will never get placed in the sorted array.
If you are going to sort numbers, you would be right. But you could think about sorting objects with this method. This is called a stable algorithm, which means that you sort the actual item from the original array. With your method, you just simply assume that their value's are same so their original position from the original array is not important. English is not my main language so I hope I explained it good enough for you to understand...
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.
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
its a sorting algorithm. so whenever you need to sort array. you use it. obviously, there are lots of sorting algorithms. but you can use it if the range is small. for further information read it details from books.
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.
Is the question like, using the number of the digit as an index to start? That doesn't work, say on this array: 093148765 01 (BLANK) 345678 Since the number 2 was skipped it wouldn't work
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?
If all you need to do is sort a list of single digit numbers, then regenerating the items like you described will work fine. However, more commonly the actual items you are sorting are larger pieces of data and the numbers you are sorting by are just the result of some comparison function. If you are sorting a list of images by date, you don't just want a sorted list of the dates. You want the dates sorted, but you still need the rest of the data in each item. The way it it is described in the video, the final values are copied directly from the original array. This means that when the number "2" is put in it's sorted position in the final array, it could just as easily be the number 2 as it could be a picture or a user object with an id of 2.
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
i don't think it's got anything to do with stablness cause it just represents numbers and the gaps between numbers. I think he mssed up in that case and no one should be looking at the starting array in part 2 (3:20) because it's unrelated and has nothing to do with ordering them either stable or unstable.
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.
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 😔
My main guess is because you may want to sort some objects by some value. E.g. tudents by age, it wouldn’t help you to get just list of sorted ages, but you want the original objects sorted by age.
... 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!
This comment made everything click. Thanks!
thx
You are a fucking hero bro! thanks!
Right? Next time I have to sort things by hand (god forbid, but it does happen), I think I'll use this algorithm, just right there on the paper.
how he find the starting index using that method ?
after watching many videos, i can proudly say that i'm still confused af!!!
you're not alone brah :/
@@BlackEswadeh I will make a video now hopefully you will understand give me a couple of minutes
dud its pretty easy
UA-cam for Counting sort - Jenny's lectures. She's explained it really well. (It's one year since your comment, do it only if you're still confused!).
skylerdj lmao
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
thank you so much, you are a god!
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!
"Simplicity is the final achievement, It's the crowning reward of art." The Guru who thought of this?
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!
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
after many articles and videos and this video I can say I got this. thanks man
I'm confused still.
saaaame
I don't know. This seems to be the best explanation I've ever seen.
you probably should switch to liberal arts than lol
@@walidzein1 then* maybe you should try some language arts videos while we're on the subject
ua-cam.com/video/pEJiGC-ObQE/v-deo.html
Hi Dojo! So would it be correct to say that Counting sort does not work for negative integers?
Correct
You could initially add a certain numbers to all the values so that the smallest is at 0. Because you are adding a constant this will make no difference in the sorted output
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??
In big O notation, only the relative relationship matters. Even though it is 2n, it is always 2n no matter what you put in. That means it can basically be factored out or ignored. Think of f(), which has a runtime of 1, and g which has a run time of 3. Even though g takes longer, they are both O(1) because it is only the relative change in the run time with respect to n. If it take 2n second to to run, what if I redefine 1 second to be twice as long? Then it only takes n seconds, which is O(n). As you can see, when you just look at the relationship they are the same.
It's kind of like how when you take the derivative of a function, any constant terms are removed. Even though x^2 + 3 is 3 more than x^2, we are only looking at the change amount of change which is the same for both.
shouldn't the space complexity be O(K)?
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 ?
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.
you're actually a genius at explaining this. Thank you!
the best sorting technique i have ever seen
Crystal clear. Thanks!
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.
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.
I know this probably isn't helpful now, but the reason is that this way lets you copy the elements from the original array. If you were just sorting integers, then it would be faster to just count them then generate the right number of each number from 0 to n. But if the list is actually a list of objects and the integers are just one property you are sorting by, then doing it this way lets you copy the objects into the right place. For example, in radix sort you need to run a counting sort on a multi digit, but with just a single digit of the number being sorted. The counting sort needs to retain the rest of the digits in the number, so you need to do it this way. There are other ways of doing that as well, but this way also maintains the relative order of the elements which is also needed for radix sort. If you don't need either of those properties, then the algorithm can be simplified accordingly.
Really great explanation!
Woah, that is really cool! So simple yet so effective!
Fabulous! This makes so much more sense than reading wikipedia or geeksforgeeks :) Great explanation!
I didn't understand from 4:11.
I understood how to find the index of the first item of the initial array in the new array based on the constructed array, but I did not understand the part about incrementing the value by 1(around 4:11).
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?
I think you should skip a number if the next number has the same starting index. In the video 2 and 3 had the same starting index because 2 did not take up any indexes.
Edit: After actually implementing the algo, I realized that this issue takes care of itself. The final step of the sort is to iterate through the original array and place each number in the OG array at it's respective starting index in the sorted array, then update the starting index for that number.
Since 2 never existed, we will never find a 2 in the original array, and thus it will never get placed in the sorted array.
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.
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~
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)
This is the best explaination ever!! Thank you very much
this was very simply and well explained. thank you!
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?
If you are going to sort numbers, you would be right. But you could think about sorting objects with this method. This is called a stable algorithm, which means that you sort the actual item from the original array. With your method, you just simply assume that their value's are same so their original position from the original array is not important. English is not my main language so I hope I explained it good enough for you to understand...
This is so easy to understand! I finally got what my prof was talking about. Thank you so much!
Do I need to keep track of the numbers that never occur in the range?
is this the same as distribution counting sort?
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.
So the only downside of this approach is that it makes it not a stable sort? Still seems like a pretty good idea to me
Simple but deep meaning....
Man, you just saved my life!!
whoever made that was high af
thank you. This makes it simple.
Holy moly. Didn't know it was this easy
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
thank you! good explanation
great video this was awesome
Amazing explanation!
This was an extremely easy to understand explanation! Thanks a lot.
Great Explanation
do we know to skip the number 2 in part two of this algorithm because it wasn't found in the original array?
can't we just print the first array on top right?
Very good , excelent teacher !!!
good work Sir ! can you relate this algorithm for real world problems and examples ?
its a sorting algorithm. so whenever you need to sort array. you use it.
obviously, there are lots of sorting algorithms. but you can use it if the range is small. for further information read it details from books.
Radix sort is perfect user of this count sort.
great explanation !
Very well explained. Loved the video
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.
Is the question like, using the number of the digit as an index to start? That doesn't work, say on this array:
093148765
01 (BLANK) 345678
Since the number 2 was skipped it wouldn't work
can u explain why do we need to shift like that?
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.
In my view this is the clearest video about counting sort algo. I don't know why so many ppl dislike this video
Bardamu, it made sense to me
@@ASOUE Glad to hear :-) There is no silver bullet in teaching methodology :-)
check this blog algorithmmadeeasy0.blogspot.com/
@@bruce2053 Thanks for the recommendation and stay safe :-)
Wonderful explanation, thanks a lot !
the title: "learn something in less than 6 mins"
the vid: 5:59😄
what is the difference between this and bucket alogirthm ?
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?
If all you need to do is sort a list of single digit numbers, then regenerating the items like you described will work fine. However, more commonly the actual items you are sorting are larger pieces of data and the numbers you are sorting by are just the result of some comparison function. If you are sorting a list of images by date, you don't just want a sorted list of the dates. You want the dates sorted, but you still need the rest of the data in each item. The way it it is described in the video, the final values are copied directly from the original array. This means that when the number "2" is put in it's sorted position in the final array, it could just as easily be the number 2 as it could be a picture or a user object with an id of 2.
thank you, we had a TA try to explain this in our class and it was terrible
Thank you so much, you saved my life
thank you so much it was extremely helpful!!
thank you, explained so well :)
Love this video, because your explanation is clear and you're doing a stable sorting algorithm
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
thank youuu !!
I got it! Thanks
what a chad
So useful! Thanks
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.
i don't think it's got anything to do with stablness cause it just represents numbers and the gaps between numbers. I think he mssed up in that case and no one should be looking at the starting array in part 2 (3:20) because it's unrelated and has nothing to do with ordering them either stable or unstable.
Count sort does not use comparisons. That is one of the big ideas here.
Thank you so much. This makes a lot of sense.
i don’t know how i got here but this looks so fun tbh
Hi bro please let me the logic "fixing malformed date string" It is more helpful for interview.
How did the channel operator become your bro?
I mean, let's say: What is his favourite food?
And how did your interview go?
please make video on peak finding
i listened to the first 30 seconds and it finally all clicked holy crap-ah-moly
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.
@Potato Tornado forgot I asked that question lol thanks for the explanation it makes sense now
But then if you get negative numbers, you are screwed
So glad it's not like my custom sorting algorithm
Genius,now i understand it!!!
THANK YOU!
best explaination
It works within the specific cases. If the series is [1,2,100000], it will fcking slow.
THANK YOU !!!!
My lecturer should draw those graphs. The text description is just confusing, I don't even know which is n which is k
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!
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 😔
This is genius
now imagine if there were no repeating numbers...
sorry,nothing understand by your video
Holy Crap (2). How the f*cking this counting algorithm works.
Amazing! I don't get it at all!
Detros we're 2.
check this blog algorithmmadeeasy0.blogspot.com/
why not just reconstruct from count?
My main guess is because you may want to sort some objects by some value. E.g. tudents by age, it wouldn’t help you to get just list of sorted ages, but you want the original objects sorted by age.
Thank you
Good explanation - thank you
Shift it to right by one cell... Nice!
Can't understand!
Actually I fully understood at min 3. Thank you!
ok so its awfully slow for alphabetical sorts
you mean fast
short and crisp
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.
*Why we need cumulative sum*?
This is sourcery, I tell you!