Radix Sort Practice

[00:00:00]
>> That is radix sort, I'm gonna give you some time now to work on the exercise, just head over to your code sandbox. Head over to the radix sort test dot js, and then we'll come back and we'll do this exercise together. So, let's do the get digit function first, so const string equals number two string.

[00:00:32]
Reason why we do this is now we can actually use chart at, right, which is a little kit that allows us to return one part of the number. You also totally could have done some mathematics with mod and that would work as well that might even be easier.

[00:00:54]
I don't know this is the way I did it, you can do it however you want to. Okay, const size equals string dot length, const mod equals, longest number, minus size and then we return string. place minus mod or 0. So now this will return, so now I can just use this getdigit function to get back a specific digit that I'm looking for.

[00:01:35]
Okay, get longest number, there's again many ways to figure this out. But what we're gonna do here is, let longest equals to 0. I mean, you could do this with a reduce. There's a bunch of ways to do this, but let's just do it with for a for loop, set like fortnight, no, it's not.

[00:02:02]
Alright, let i equals zero, i is less than My get longest number right should be an array is less than array dot length i plus plus and then counts current length. Length equals array at i dot 2 string dot length, right. So if this was 3000, this would return current length would be 4, right?

[00:02:44]
And I'm just looking for what the longest number is there so I can know what to provide get digit up here. Okay, and then I'm gonna say, longest equals current length. Is greater than longest, then it's gonna be equal to current length, otherwise longest. This is a ternary for those of you that are not familiar with it, it's just a condensed if statement right?

[00:03:19]
So if current length is longer than the new longest will be the current length otherwise it will stay what it already was which is longest. You could totally put this in an if statement as well, I just like turn arrays, okay, then down here we return longest. So now we have a function that'll get us the longest number in array, cool.

[00:03:48]
Const longest number is equal get the longest number with the array. So that's that, okay, here we just need to create the data structure that we're going to use. I just did like a little shortcut here a const buckets equals new array. Of length 10 dot fill, Dot map, And this will just fill it with brand new empty arrays.

[00:04:36]
You totally could have made a for loop or something like that would make these buckets as well, but suppose we say this line 42 all it does is it creates an array of 10 empty arrays, right? Cool. So let's do this then we'll do a for loop, let i equals 0.

[00:05:10]
I'm sorry, let i equal longest number minus 1. I is greater than or equal to zero, i minus minus. So we're gonna start like if this is, 4 is the longest up here, then we're to start at 3, we're going to go down to 0, okay? First thing in here is while there's something in the array.

[00:05:43]
So while array dot length. We're gonna say const current equals array dot shift, so we're gonna pull the first thing off the array, I'm gonna say buckets, Getdigit, Current, i, longest number. Calling this getDigit function that we have up here, right? Dot push current, okay, so we'll have those ten arrays, right?

[00:06:25]
And we're just enqueuing it somewhere into one of these, right? So if this was like this one here, let's say 1244. For the first iteration, it's going to grab this four number and it's going to push it into the four spot, the four buckets, right? And then when we're done, we will pull that back out.

[00:06:48]
But let's see the going back to our little graphic here. It's this part that we're doing, the part where it's pushing it in. Right, that's what this first enqueuing is doing. So we're pushing into these 0 through 9 buckets over here. Okay, that's what that while loop is gonna do.

[00:07:14]
So after this is done, we're gonna have all of our numbers bucketed by whatever place we're sorting by. Okay, and then we have to go ahead and dq all of these, so we're gonna say for let J equal zero. J is less than 10 J plus, plus, you could also say,buckets dot length, but it's always going to be 10.

[00:07:47]
Right, unless you're gonna be like doing hexadecimal bucket sorting. I mean you could there's no reason why it wouldn't work. Why while, buckets, J dot length, you're just going to pop them off. Array dot push buckets J shift, so we're going to be taking them off of the front of the buckets and you're going to be pushing them onto the array.

[00:08:32]
Then down here you are going to return array. All right. So let's make sure that this is not auto running, we're gonna take this off of skip. And we're gonna see if we can run this code under radix sort make sure that this actually is running radix sort right there works.

[00:09:14]
So, let's take this one off to see if it works with even bigger number sets. Run it again and looks like it's still working, cool. So just for fun, I'm gonna copy all of this. Ones that don't need that and let's hop over to our sort visualizer because this actually will work for that.

[00:09:47]
And paste this over here and I'm just going to call this sort instead of radix. Okay, and then we'll head over to our little browser here, we'll click on sort. And let's also modify this just a second with this. Okay, and then here, when I call it with sort nuns.

[00:10:41]
And then here we do have to snapshot. So, we'll first snapshot with the array, snap shot array and let's snapshot at the end of all every one of these snapshot. Here with the array, so we're only getting seven unique snapshots, right because we're only doing it at the end of all the bucketing and D bucketing.

[00:11:13]
We could code up a more capable bucket visualizer but this is what we have for right now. But notice after one iteration all the zeros are at the beginning 1, right, 2,3,4,5, right, and then after the second iteration, it's 0,01,02,03,05,06. Right, after the third iteration, it's sorted by the hundreds, so 001,002,008, so on and so forth.

[00:11:51]
After the third iteration, it's sorted by the thousands than the tens of thousands. And then afterwards, this bottom one is totally sorted. Pretty wild, right, I can't imagine how people come up with these things. So the question is, what's mod here, I didn't know what to call it.

[00:12:15]
[LAUGH] Because you need the last number in the array and then we're counting backwards, right? Which is a weird way to do math and code, right. So on the zero with iteration I need the ones place which is going to be the last index in the string, right?

[00:12:33]
So if I have, let's say, the longest number is 100. And I'm asking for the zero with element, actually the two index of that string, right? So, this took me a bit of trial and error to get this exactly right. So if it took you some trial error or you didn't find like couldn't figure it out, I do not blame you.

[00:12:55]
This actually probably took me 20 minutes of just like following my brow with my computer before I finally figured it out. Valid question, does this kind of defeat the purpose of the entire sword like in terms of like its complexity? Let's go with yes and no, sorted slash, it depends, right, everyone loves that damn answer now.

[00:13:17]
One, you're not really doing much heavy lifting here, right? Like you're not doing any comparisons, you're not doing anything like that really you're just asking for the length. So on one hand, not particularly, on the other hand, you are looking at every number here and grabbing the lengths.

[00:13:35]
We do need this longest number just to make sure that the math here is correct. I'm sure there's probably a more efficient way of doing this. But this is already hard enough to conceptualize. So I wanted to kind of take a shortcut so that you all could probably focus on the more important part of this, which is the bucketing part of this, but you could probably What do I want to say here, you could probably combine this into one more effective function.

[00:14:07]
Right, but I didn't wanna overload you with with concepts here. And in other words, I haven't thought of a better way to do it but there probably is one. But I guess another thing I would say is like if you were actually deploying radix sort in production and you were writing the code yourself.

[00:14:27]
You'd probably have to have some knowledge beforehand of what kind of ranges of numbers you'd be dealing with, right? Well, I imagined many of you did get met and some of you probably didn't get it as well. That's totally fine, this is kind of again, a difficult one to conceptualize.

[00:14:45]
But hopefully you're grasping at least the the method here, right? I'm actually less concerned that you successfully pass the unit test and I'm more concerned about does the sort makes sense to you. Like that's the most important thing here is like this, this kind of pattern of like, hey, let's take this apart and compare things piece by piece, right?

[00:15:07]
That kind of concept is one that I really want you to walk away with here, because that actually could be useful to you later while you're writing code somewhere. You also totally could write radix sort for something like strings, right? Instead of queueing this buckets here, in an array of 10, this could be an array of 26.

[00:15:28]
If you're doing like the English alphabet, right? And you could do bucket sorting that way, or radix sort rather using letters, right, that totally works as well or hexadecimal. And it would be 16 buckets or binary actually, binaries are really effective. Use case for this, right, because you would just be queuing zeros and ones, right?

[00:15:53]
We should go pretty fast, so, yeah, just another interesting kind of arrow to keep in your quiver.