Radix Sort

[00:00:00]
>> The next Sort that I wanna talk about with you is one called Radix Sort. Sometimes this is called Bucket Sort, though actually technically Bucket Sort is something different, but it's very similar. In any case, this is something called a non-comparison sort, in that you'd never actually directly compare numbers to each other use a method called bucketing.

[00:00:29]
And you can see kind of see that happening here, it's really strange. So you can't even really measure it with big O in the sense that, it's not gonna be N squared, or anything like that, it's actually going to be I think, MK? [LAUGH] But we'll get into that here in just a second.

[00:00:46]
So yeah it's a non-comparison sorting. We do something by actually comparing different number of places instead of comparing numbers directly. And I'll get into that here in just a second. So we're gonna sort parts of the array first, right? So let's take a look at this array that I have here in my notes 109, 224, 901 and 58.

[00:01:11]
So the first thing that you're gonna do is you're actually going to sort it by the ones first. So 9, 4, 1, 8. So you can see here, after the first pass, we have 901, 224, 58 and 129, right? So you can see it's actually sorted by the ones place.

[00:01:33]
Then we're going to sort it again but by the tens place, right? So after the second round, we have 901, 109, 224 and 58, then we're gonna sort of one more time by the hundreds. So at this point we'll have 058, right? 000 here, 109, 224 and 901.

[00:01:58]
And you can see after having done that, sorting it by the hundreds place which is the largest place that there is we end up having a sorted array. Kind of a mind bending way of sorting. It's not something that a human would ever kind of think of directly.

[00:02:16]
So you can kind of see that happening here. It'll sort them into buckets by zeros, ones, twos, threes and fours, and you do it for however many places there are. So in this particular case, there's up to 1000. So we do that sort four different times. Makes sense?

[00:02:40]
Sort of? So, again, what's the big O of this? The big O of this is gonna be a little bit different than we're used to because we have to account for this how many buckets or how many times we have to do the sorting, right? So we're gonna call that term k or w in this case, let's just go with k.

[00:03:09]
And instead of being On squared, you end up being which is n times n, you end up being n times k. So it's kind of n squared in the sense that it's two different terms multiplied to each other. So you might ask me, is this better than n log n?

[00:03:26]
Well, as you may have guessed being this fun of the course, it depends, right? It depends on what the distribution of your numbers are, right? So if you have a lot of very long numbers that are distributed really well, right? So there's like kind of a uniform distribution with lots of terms, right?

[00:03:46]
So if you have, hundreds of 1000s that are distributed across that entire range, then radix sort actually ends up being a pretty good sort. But if you're sorting 500 numbers and they're all between 0 and 100, it tends to be kind of inefficient and you'd be better off with something like quick-sort or something like that.

[00:04:09]
So, spatial complexity n being n plus k, where n is the length and k is how many places there are to sort by. So it's not great on spatial complexity because you have to do a lot of bucketing. So that's why it's only favorite employees specific circumstances. But I wanted to show you how you can sort things without actually ever directly comparing numbers, right?

[00:04:40]
So like in this case, 109 is actually never directly compared to like 901, right? The only thing they're ever compared by is just by these buckets. So I'm gonna give you a chance to try and code this up. I'm gonna help you kinda get started here. That's fine.

[00:05:08]
And actually, I'll just come back to here. That was quick-sort. Let's get into radix sort. Okay, so you can see here, these are all the numbers that you're going to be sorting by. And if you wanna just do something for fun here, you can actually do this. It'll just sort 99 very long numbers for you.

[00:05:32]
So you can see how efficient this actually can be. But this is kind of extra credit down here. Let's focus on this one up here. Okay, so we're gonna do a radix sort here. So, I'm gonna just advise you on some helper functions I think you should code for yourself.

[00:05:59]
One should be function getDigit. We give it a number, a place, and the longest number. So for example, if I put into let's say I have a number like 1391, so that would be the number. And I give it a place of 0 cuz I want the 0 with place.

[00:06:36]
And I have the longest number in here. It's like, correct my doing got to make sure I'm doing this right way. And then the longest number in here. So the longest number would be like the longest number in your particular set rise. So if I had a number like 30,000 in my set, or let's even look at this, the longest number in this set is of length 4, right?

[00:07:12]
So 3000, 1244, so the longest number in that particular case would be 4. Actually is there. And 4 in this getDigit that should return here. The one right? Number equals that place equals that and longest number equals 4 Sorry, I'm just making sure that I get this correct.

[00:08:07]
Anyway, this getDigit helper here is gonna help you here. So that you can just provide these numbers here so that it helps you with the bucket sorting. Then I would also just write a function called get longest number? A lot of times you'll know this going into your data set, right?

[00:08:27]
You'll know that the longest stuff will be of length 4, length 5, or length 6 or something like that. But in this particular case, I will just provide that here, get longest number And in this particular case, get longest member if you call it on this data set, it would return 4, right?

[00:08:56]
Right, the reason why you need longest number here, that's what I was trying to remember is, let's say the longest number in your data set is 3000 but you give it number 3, right? So the longest number here is gonna, or so not the longest number, but the place will be 4 on that.

[00:09:13]
So you'll actually get back to 0, does that makes sense? Okay, and then let's go into what radix sorting is gonna do. So find the longest number Create how many buckets you need. In our case, since we're doing base 10 math, this will be an array of arrays.

[00:09:52]
Right and then you'll have a bucket for 0123456789. Okay, then here you'll have a for loop For how many iterations you need to do. So that will be based on the longest number, right? Because you need to do one iteration for each of the longest numbers. And then basically what you do is you gonna throw them in the buckets and then you're gonna dequeue them back out into your final results.

[00:10:22]
And you'll keep doing that back and forth until you end up with the correct answer. So inside that for loop you'll have Nq, which is the word for just like throwing something into an array the numbers into their buckets. This will probably be a while loop. That's why I have that.

[00:10:59]
And then here we're gonna have another for Loop, For each bucket where you dequeue all of the results. That's more or less kinda step-by-step what you're going to be doing. I kinda diagram this modality because it's kinda an abstract one to think about. But the idea again, let's just go back to our visual here to kind of just take this step by step.

[00:11:38]
So notice for each one of these, it's enqueuing them I just make that bigger. There we go. First by the 0's, right? 0's, 1's, 2's, 3's, 7's, right? You can see the highlighted in red of the one that it's enqueuing at the moment. Then, what it does notice, it just dequeues them out in order, right?

[00:12:06]
So, all the 0's are coming out, all the 1's are coming out. And so after the first iteration we have this array that's sorted by the 1's places, right? And then it does it again, notice that the red ones are now the 10's, right? So now we're sorting by the 10's place.

[00:12:25]
And that goes back into these buckets. Notice that nothing's ever being compared to each other. We're never asking, is this bigger than this? We're just putting in, into the buckets and then back out into the general results already. Okay, so this gets put back into these buckets by the 10s place.

[00:12:43]
Notice that 1and 7 are in the 0, right because they have no 10s place. And then these just get dequeued out again. And now notice that it's sorted by the 10s and the 1s place right so 1, 7, 10 20, 21, 20, 22, 27, 30, 38, 43, 77, 80, 82, 93, 99.

[00:13:06]
And then we do it again for the hundreds. And then notice that it's sorted now by the hundreds. Right, notice that 793 is the last one in here now. Whereas one is still the first one, and then you do it one more time for the 1,000s place. And then you dequeue all that back, and there you go.

[00:13:31]
Now everything is sorted without ever asking is this bigger than this? There's no If statements in there, it's just putting things in in and out of buckets.