Learn Counting Sort Algorithm in LESS THAN 6 MINUTES!
ฝัง
- เผยแพร่เมื่อ 20 มี.ค. 2017
- Step-by-step guide to counting sort with a visual example. Counting sort is useful when the range of values each item can take is very small.
For example, you can use if if you want to sort 10,000 people according to their age. We can safely assume (for now) that no human is older than 199 years old, so the range of values is very small in this case.
... 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
TH-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
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
thank you so much, you are a god!
"Simplicity is the final achievement, It's the crowning reward of art." The Guru who thought of this?
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.
you're actually a genius at explaining this. Thank you!
This is so easy to understand! I finally got what my prof was talking about. Thank you so much!
Woah, that is really cool! So simple yet so effective!
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 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
Do I need to keep track of the numbers that never occur in the range?
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 was an extremely easy to understand 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?
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~
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!
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 is the best explaination ever!! Thank you very much
Love this video, because your explanation is clear and you're doing a stable sorting algorithm
this was very simply and well explained. thank you!
Amazing explanation!
Wonderful explanation, thanks a lot !
Very good , excelent teacher !!!
Thank you so much. This makes a lot of sense.
Very well explained. Loved the video
Man, you just saved my life!!
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
th-cam.com/video/pEJiGC-ObQE/w-d-xo.html
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
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 ?
thank you so much it was extremely helpful!!
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.
please make video on peak finding
can u explain why do we need to shift like that?
thank you, explained so well :)
thank you. This makes it simple.
shouldn't the space complexity be O(K)?
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
what is the difference between this and bucket alogirthm ?
thank you! good explanation
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)
Holy moly. Didn't know it was this easy
Great Explanation
Good explanation - thank you
great explanation !
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.
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!
is this the same as distribution counting sort?
Genius,now i understand it!!!
Simple but deep meaning....
THANK YOU!
whoever made that was high af
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
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.
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
i don’t know how i got here but this looks so fun tbh
Shift it to right by one cell... Nice!
that's fantastic
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
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?
can't we just print the first array on top right?
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...
Thank you
i listened to the first 30 seconds and it finally all clicked holy crap-ah-moly
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.
best explaination
Actually I fully understood at min 3. Thank you!
So glad it's not like my custom sorting algorithm
Count sort does not use comparisons. That is one of the big ideas here.
This is sourcery, I tell you!
short and crisp
That was good.
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!
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.
How did the channel operator become your bro?
I mean, let's say: What is his favourite food?
And how did your interview go?
Take my kneel...
It works within the specific cases. If the series is [1,2,100000], it will fcking slow.
Holy Crap (2). How the f*cking this counting algorithm works.
This is magic...
This is genius
This is epic
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
Amazing! I don't get it at all!
Detros we're 2.
check this blog algorithmmadeeasy0.blogspot.com/
now imagine if there were no repeating numbers...
it took me 6 minutes and 1 second.
why not just reconstruct from count?
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.
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.
the title: "learn something in less than 6 mins"
the vid: 5:59😄
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.
But then if you get negative numbers, you are screwed
I think I should give up on this sorting technique.
Can't understand!
*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.
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 :-)
1:35