This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Radix Sort" Lesson
[00:00:01]
>> Brian Holt: Welcome back, and congratulations, you've survived so far. You deserve a merit badge of some sort. Lastly, we're gonna do one last sort called a radix sort. This is a very different sort than what we've been looking at previously. It's called a non-comparator sort. So it isn't n log n.
[00:00:24] It can't be [COUGH] anything like that. In fact, something that's interesting about comparators versus anything else, is when you're doing comparisons, the reason why something is n squared is because I'm taking one item and I'm comparing it to every other item in the array. That's what makes an n squared sort.
[00:00:45] If something is n login, it looks at every item at least once in the array, which is where the n comes from. Mathematically, that must happen. And then I'm only comparing it against some other items in the array, using that to make assumptions, that if this item is bigger than this one, then it's definitely bigger than the other one.
[00:01:05] Using those mathematical properties to only make some comparisons. They've proven that using comparator sorts, that the fasted you can go is n log n. It's mathematically impossible to go any faster. Everything else is just making the coefficients. You're only doing slightly less instructions, but you still have to do the same amount of comparisons or at least there is an absolute floor to that.
[00:01:30] Radic sort is quite different in that, it doesn't actually make any comparisons. It's never comparing one thing versus the other. It's doing some different some orthogonal sorta thing that makes it so that you can actually go faster in certain circumstances. Now, I'm gonna show you the more simple way of doing this but you can actually get this to go even faster than what I'm going to show you.
[00:01:55] So first thing you must be asking is like, how do you faster versus how do you sort something but never comparing anything. And it's kind of an interesting methodology. Something that I would have never thought of but let's chat about it. So assume that we have an array that looks like this.
[00:02:18] 10, 1, 52, 102, 33, 45, 6, 18 and 9. What we're going to do is we're going to create 10 queues. You're probably sick about hearing about queues by now but deal with it you have one more to deal with. I'm then going to un unqueue each one of these items in 1 of 10 different queues based on solely the 1 place.
[00:02:46] So let's look down here at this little example right here that I have in the documentation. So I'm going to create ten queues, one for each number that is possible. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. And I'm going to unqueue each one of those based on solely the ones place in each one of these queues.
[00:03:11] So this 1's gonna go in the 9 queue and these 2 are going to go in the 7 queue. And they just go in in the same order that they're in the array already. Once I've unqueued all of those then I'm going to dequeue all of them in order so they're gonna come back out as just like you see here 347, 457 and 359.
[00:03:32] It's the same order but I did the 7's first and then I did the 9's. Does that make sense? So actually if you look at this, it is sorted by the ones place. If you just ignore the rest of the number, it is sorta based on it, cuz you have 7, 7, 9.
[00:03:49] I'm then gonna go through and unqueue these based on just the tens places, ignoring the ones place. Ignoring everything to the left and just unqueue everything, this one's going to go in fours, this one's going to go fives, this one's going to go in fives. Then I unqueue those into those and then I'm going to dequeue, again, them in order.
[00:04:10] So that's actually ends up being the same order, but I dequeue them in that order. So 4, 7, 5, 9 and 5, 7. If you look at this, ignoring the 100s place, they are in order. 47, 59 and 57. Why did this get out of order? This isn't correct.
[00:04:42] Let's go in reverse, anyway, I assure you it will be in order. Lastly, you go through, it's because I'm one step ahead of this so 47, 57 and 59, that's what I was getting mixed up about. So 47, 57, 59, it's not in order cuz of the hundreds are different.
[00:05:07] But I'm gonna do the same thing with the hundreds place and once I've done that then it's 347, 359 and 457. So at that point, once I've done it based on the 100s then it just comes out in order. So that's more or less what's kinda happening, is like put the ones in order, put the 10s in order, put the 100s in order.
[00:05:25] And because you're going in that particular order, everything comes out in order. Is that following, does that make sense?
>> Speaker 2: So it depends on how many places you have, how many times it'll take to sort it?
>> Brian Holt: Right, so the first thing you need to do is you need to go through and find the longest number.
[00:05:41] And that's how many iterations you're gonna have. So let's say this was 1,457, you would have an extra iteration and these ones would just go in the 0 bucket. Does that make sense? Cool. There's all sorts of micro-optimizations that you could do to get this to go even faster, but we're just gonna do radix sort to completion.
[00:06:01] That's kind of the gist of what we're gonna do here. And that's the whole algorithm. It's just unqueueing and dequeueing things based on buckets. So the more buckets you can have, the faster this algorithm can go which is why it's doing this in binary it's actually faster than doing it in decimal which is what we're gonna do.
[00:06:18] We're still gonna do it in decimal because I don't wanna teach binary on top of radix. So I'm gonna give you a second to
>> Speaker 3: Binary's faster, but you said more buckets is faster.
>> Brian Holt: I guess more iterations, more iterations upon the buckets. Because you can have longer and longer numbers.
[00:06:39]
>> Speaker 3: Okay.
>> Brian Holt: Yeah. That's a good clarification, for sure. So that's what we're gonna do here. You could implement it in terms of binary if you like. And you can call snapshot to see what this actually looks like on implementation. I'll give you a shot now to go do that.