Linear Time Sorting: Counting Sort, Radix Sort, and Bucket Sort

  Рет қаралды 16,183

Algorithms with Attitude

4 жыл бұрын

Table of Contents:
00:00 - Introduction and Prerequisites
01:01 - Counting Sort
05:45 - Stability
08:45 - Radix Sort
09:36 - Most Significant Digit First
11:32 - Least Significant Bit First
14:28 - Bucket Sort
17:13 - Broken Lower Bound?
18:40 - Bucket Sort for Counting Sort Input

Пікірлер: 38
@andreytamelo1183
@andreytamelo1183 3 жыл бұрын
By far the best and most complete explanation I've heard. Awesome!!
@umutkavakli
@umutkavakli Жыл бұрын
Unbelievable. Just unbelievable. I couldn't have expected that I would be so satisfied with this randomly selected video. Best explanation ever!
@AlgorithmswithAttitude
@AlgorithmswithAttitude Жыл бұрын
Thanks! Over the last few years, you and dozens of others have enjoyed it!
@Boneplayer123
@Boneplayer123 3 жыл бұрын
I’ve watched this video at least three times, and it gets better every time! Please don’t stop making videos.
@AlgorithmswithAttitude
@AlgorithmswithAttitude 3 жыл бұрын
But if it was reeeeaaaally good, maybe you would only need to watch it once? The school year is now taking all of the time I have to give, and a bit more. I was able to make videos last year by not teaching for a bit, but I don't see myself having time to make more this semester, and likely not for the academic year. After that, maybe they will come slowly for another couple years, and then another window when I try to make a whole bunch. But, by then, maybe there will be other channels with similar content that aren't videos of lectures. For this very topic, I saw a video that just came out just a week or two ago, and if it had been available 6 months ago, I might not have made this one.
@manojkumar-lt6wk
@manojkumar-lt6wk 3 жыл бұрын
​ @Algorithms with Attitude can you share the link to that video?
@AlgorithmswithAttitude
@AlgorithmswithAttitude 2 жыл бұрын
@@manojkumar-lt6wk I don't think I saw your comment until now. With a quick search...I don't know what video I was referring to, sorry.
@farruhhabibullaev5316
@farruhhabibullaev5316 2 жыл бұрын
By far the best content on counting, radix and bucket sorting.
@annawilson3824
@annawilson3824 2 жыл бұрын
This was truly EPIC! As if you took the algorithm, and expanded it in the Taylor series, to explain each piece individually, thank you, prof. Taylor!
@vaa33nn65
@vaa33nn65 3 жыл бұрын
bruh holy shit this is my first video for this channel and i already love this guy XD
@eloskowy4954
@eloskowy4954 2 жыл бұрын
This video is truly a masterpiece.
@doggie01031
@doggie01031 2 жыл бұрын
Wow! Great video - super clear explanation! Thanks
@jasonli1060
@jasonli1060 3 жыл бұрын
this clarifies a lot, thank you!
@pawekonopka5028
@pawekonopka5028 2 жыл бұрын
Great work, sir!
@yanivsh
@yanivsh 3 жыл бұрын
One of the best presenters ever!
@steven1146
@steven1146 Жыл бұрын
really clear explanation. Thank you so much.
@hapysethi1306
@hapysethi1306 2 жыл бұрын
Thanks for the explanation!
@imganesh12
@imganesh12 6 ай бұрын
Easiest explanation❤
@Supakills101
@Supakills101 10 ай бұрын
I finally understand now!
@poojamoorti8205
@poojamoorti8205 3 жыл бұрын
you are a FANTASTIC teacher wow
@AlgorithmswithAttitude
@AlgorithmswithAttitude 3 жыл бұрын
Some of my students beg to differ...
@AlgorithmswithAttitude
@AlgorithmswithAttitude 3 жыл бұрын
@Shyam Vyas You have badly misspelled "teaches".
@XieQiu
@XieQiu 4 жыл бұрын
wow didnt know you came back!
@AlgorithmswithAttitude
@AlgorithmswithAttitude 4 жыл бұрын
I took some off from teaching to make some more videos. They take me so long that it is hard to do while teaching.
@stormblessed30
@stormblessed30 4 жыл бұрын
Online classes under you would be interesting ngl
@AlgorithmswithAttitude
@AlgorithmswithAttitude 4 жыл бұрын
Thanks. I haven't tried full online classes, just a flipped class where we do exercises in person, but these videos serve as the lectures.
@manojkumar-lt6wk
@manojkumar-lt6wk 3 жыл бұрын
what is the different version of counting sort that is unstable you were talking about at 6:20?
@AlgorithmswithAttitude
@AlgorithmswithAttitude 3 жыл бұрын
Instead of going through the array left to right, or right to left, and placing it in a new array, you can grab an arbitrary number, see where it needs to go using the index array, copy out whatever is in THAT location, and overwrite the copied value with the number you started with. Then place that copied value wherever it needs to go in the same way, until eventually something overwrites the location you started with. The entire array will break down into cycles like this, once every cycle has gone once, you are done. (I haven't thought about how to code it nicely.)
@LinusTan94
@LinusTan94 4 жыл бұрын
Radix sort is the best waifu
@emmaguo619
@emmaguo619 3 жыл бұрын
At 16:26, should it be "Over 36% of buckets with 0 item. Over 73% of buckets with 1 item and fewer. Over 91% of buckets with 2 items and fewer. Over 98% of buckets with 3 items and fewer......."?
@davidtaylor2809
@davidtaylor2809 3 жыл бұрын
That wouldn't be nearly as useful. If I told you that 99.9% of buckets had 1 or fewer items, would it help? Not if 1 bucket had all of the items, and the rest of the buckets were empty. We are less interested in lots of small buckets, and more interested in lots of items being in small buckets.
@nextswe504
@nextswe504 4 жыл бұрын
Visual animations are really helpful, but i think it would be better if we can get better focus on those animations. For example: i had to pause multiple times to see the value changing inside those yellow boxes :) . Hope to cover all your videos gradually.
@AlgorithmswithAttitude
@AlgorithmswithAttitude 4 жыл бұрын
What time were you pausing? You could also try watching the animation at a lower speed. Probably there is something I should have highlighted more, I'm kind of making it up as I go along.
@nextswe504
@nextswe504 4 жыл бұрын
@@AlgorithmswithAttitude Since you are using yellow and black border, sometimes those border does not get too much visibility. I think it's more like an ux issue than animation. Giving thick border with some strong color might resolve the issue. I have emailed you a screenshot. In the screenshot you can get some idea about the issue. Since the issue is too subtle, it's easy to miss.
@AlgorithmswithAttitude
@AlgorithmswithAttitude 4 жыл бұрын
Thanks. It would have been trivially easy to make those borders much bigger, and to include a color change, this is constructive. That video is still relatively new, I could re-edit it and upload a new one, though that is slightly less trivial. I'll think about it, but will try to highlight animation changes more from now on.
@nextswe504
@nextswe504 4 жыл бұрын
@@AlgorithmswithAttitude You can do that for future viewers but i have already completed this one... 😇 . Many many thanks for your videos. Keep them coming. If you can do some series on Backtracking & Dynamic Programming that would have been great. In my search i couldn't find many resources about these topics.
@AlgorithmswithAttitude
@AlgorithmswithAttitude 4 жыл бұрын
I just published my first dynamic programming video last week, and my 3rd one a few minutes ago. Check my playlists. I will add one more this week. There should be a bunch more added eventually, but I will only get to 1 more this week before changing topics. The others won't be there anytime soon.
@niloofarshaghaghi4870
@niloofarshaghaghi4870 3 жыл бұрын
if i don't flunk tomorrows exam it's thanks to you (and cheating but mostly you)
Khó thế mà cũng làm được || How did the police do that? #shorts
01:00
БОЛЬШОЙ ПЕТУШОК #shorts
00:21
Паша Осадчий
Рет қаралды 8 МЛН
Sigma Girl Past #funny #sigma #viral
00:20
CRAZY GREAPA
Рет қаралды 32 МЛН
Khó thế mà cũng làm được || How did the police do that? #shorts
01:00