Four Semesters of Computer Science in 5 Hours, Part 2 Radix Sort Solution

[00:00:00]
>> Brian Holt: Coming here, this takes about 50 lines of code to do.
>> Brian Holt: So the first thing that you want to code up here is you wanna do like a getDigit, cuz you're gonna be using getDigit a lot. So function getDigit (number) place and the longest number.
>> Brian Holt: So the number's just gonna be the actual number.

[00:00:28] The place is, I want the zeroes, the tens, the whatever. And the longest number is going to be the be the longest number in the entire array that you're sorting, right, because that's important. The reason why that's important is like if I get 10 and I'm sorting in the 3 place, I'm just gonna give you back the 0, right?

[00:00:49] So const string, so this is far more easily done using string manipulation. So I'm just gonna say number.toString. Const size = string.length and then here, I'm gonna say const mod = longestNumber- size, so,
>> Brian Holt: The only reason that I'm doing that is if I'm looking at something that's in the ones place, if 1,000 is the largest number, I need to be looking at the second element, right?

[00:01:33] I can't be looking at the fourth element, because that would be out of index. That's what the mod is for is basically, the longest number minus the size to make sure we're getting the last index, right, so that everything lines up correctly. So that's why you say return string [place- mod], or 0.

[00:01:53] Cuz if that's out of bounds, then you just return 0, right?
>> Brian Holt: So that's what that getDigit function does.
>> Brian Holt: Then here,
>> Brian Holt: In radixSort.
>> Brian Holt: So const longestnumber
>> Brian Holt: Equals findLongestnumber, that's, write that up too. FindLongestnumber of the array, so I think I have that up here, yep.

[00:02:33]
>> Brian Holt: There are more efficient ways of doing this. This is just kind the instructional way of LongestNumber(array). So let longest = 0. Then we're just going to go through and find which one two string length is the longest. So const current, let i = 0; i < array.length; i++).

[00:03:11] Okay and then here I'm gonna say const currentLength
>> Brian Holt: Equals array[i].toString().length, okay? And longest is equal to currentLength. So if it's longer than the current length, then we're just gonna make it the longest one, so, if it is, then it's equal to current length. Otherwise, it's just whatever it was previously longest.

[00:03:46] Okay, and then after that, we return the longest number. Eventually this will be like five, right. If it was 10,000 that would be the longest one then we would return five here. Okay, so that's what longest number is. That's what we're gonna use there, then I'm gonna do buckets, const buckets = new array.

[00:04:11]
>> Brian Holt: 10, cuz that's how many it could be and actually, there's an even easier way to do this.
>> Brian Holt: Array, so you can do Array.from{length: 10} and then you give it a map function just like you would for a map reduce and you return a new array.
>> Brian Holt: So what buckets is going to be, it's going to be an array of 10 arrays, right.

[00:04:44] That's what this does.
>> Brian Holt: Okay, then here I'm gonna say for(let i = 0). Sorry, (let i = longestNumber), cuz that's how many iterations we're going to have. longestNumber- 1, i is greater than or equal to 0, and i Okay, and then you're gonna say while(array.length)
>> Brian Holt: const current = array.shift, so I'm gonna take this out of the current.

[00:05:31] Where did I set current? That's what I'm doing, const current is the first item in the array. Then I'm gonna say buckets(getDigit(current, i, and longest number)).push(current) right? So what this is going to do is it's going to go through and bucket every single number based on which bucket it should be in, right?

[00:06:04] Cool, does that make sense? So if this one was 801 and we're looking at the 10's this is gonna go in the 0 bucket, right? So this is gonna give me back 0. This is going to push an 801 into that bucket in order. The order here is really important, otherwise, it's not sorting.

[00:06:22]
>> Brian Holt: Okay.
>> Brian Holt: Now, what I'm gonna do for each one of those as I'm gonna say for (let j = 0; ). j < 10; j++. I'm gonna go through and dequeue each one of those. I'm going to say while (buckets[j].length), I'm gonna say array.push(buckets[j]) shift. So I'm just gonna go and dqueue all of those into the array.

[00:07:12]
>> Brian Holt: Then here, if you wanna see the cool visualization you just call snapshot(array). Cool, I think that should be everything that we need to see. Let's take a look and see if what happens.
>> Brian Holt: And it passes. So you can see here that nothing is in order just kidding.

[00:07:39] It goes the one down here at the bottom is everything is in order, yeah?
>> Student: What is the time complexity of this?
>> Brian Holt: So this one's a little bit more difficult to describe. If we go to Big-O cheat sheet, great website, good for these sorts of things. If we go down to Radix Sort, it has this thing called k.

[00:08:02] So that's what I was referring to is it's not really a apples to apples comparison. If you're doing something like Heapsort, or Quicksort, or Mergesort, it depends on how well you can bucket it. So that's what the case represents, is how many buckets you can have, right? So in this particular case, I had ten buckets, but there's a lot more complexity that it's kinda trapped in that case.

[00:08:25] So it depends on how you can bucket it and those sorts of things. So MK is the answer to that. I'm not gonna get to much more into it because I don't really understand it much more than that. And if you wanna see what it looks like. It looks a little bit cooler in my opinion when you have a lot more numbers, so let's do this.

[00:08:51] By the way, you can only run one of these at a time, just because I wrote it really quickly. It's the fault of the visualization thing, not the fault of Radix sort. You can Radix sorts a lot of time. So what's pretty cool is, again, after the first iteration, you can see all the 0s are up front, then all the 3s, then the 6s and blah, blah, blah, etc.

[00:09:13] And then the second time you can go through the 01, 02, 05, and be like 19, 20, 22. So you can see it kinda gets slowly more and more sorted based on the 0's place, the 10's place, all that kind of stuff until eventually everything is actually in order.

[00:09:30]
>> Brian Holt: Pretty neat in my opinion.
>> Brian Holt: Cool, whoever asked that question, it was a good question, the complexity question.