Implementing QuickSort

[00:00:00]
>> And I think that's all we have to do with it except other than the fact that I'm gonna tell you this really cool story. All right, so this real cool story is that I was on a team that was the first team to be a non-MIT student team to make it to MIT's final finalist in MIT Battlecode.

[00:00:17]
So Battlecode is where you program these little computer robots. They're like simulation robots. And they have to battle it out and you have to do all this different type of fighting, there's macro kind of, it's like imagine StarCraft, right? It's like Starcraft but for people that aren't smart.

[00:00:31]
And so it's like really really simple and there's very few conditions, there's no races, it's just like people in a base often. There's every single year it's a little bit different. Sometimes there are races, sometimes there aren't, blah blah blah. It's pretty cool. And when we were doing this, I had this thing where if a certain resource was between us and our opponent, then I'd want to capture that and turn it into a turret, right?

[00:00:55]
So if they tried to come near us, we'd be able to shoot them really easily, super, super easy. They couldn't get us, it was a way to just dominate them, right? And so I thought, Okay, this is what we're gonna do. I could take all of these different resources that are on the map.

[00:01:09]
And I can just simply sort it and find which ones we need to do certain different things with. It should be really, really simple, right? Well, of course, the constraints with MIT Battlecode is that you only get 10,000 bytecode operations. This is in Java, everyone loves Java. Which means you actually get very few things you can do any one turn per person, so I couldn't QuickSort it.

[00:01:29]
Within like five elements the guy would come out of the base and then just sit there for like 20 frames and just be dead in the water. And then as the base got more of them, sometimes they just stopped and then our whole thing would stop and then we'd just die.

[00:01:41]
Like what is going on here? And it came down to the sorting algorithm. You couldn't simply sort because you'd run out of time, you'd run out of computational that's available per turn. And so what I realized is that if you look at this thing, what you're gonna see here is that this is just a tree, right?

[00:01:56]
This is just a tree filled with states, and so if you really think about it, you don't have to do this recursively. You just simply need to know where you start, where you end, process that thing, and it may produce two children. If it produces two children, add it to a stack and then you can actually get the exact same thing.

[00:02:17]
And so that's all I did was every single turn I'd go hey, how many do I have left? Which there was a function to say how much computation you had left. And if I was like hey, if it's below 1,000, then don't do any more sorting. Go through your other things so you can like move around.

[00:02:31]
You can see if there's bad guys near, you can do other operations without running out of space. And so it became this kind of like, simple way to avoid running out of space. So these things do become useful. Obviously, that is an obvious case in which it's so specific you'll probably never run into it.

[00:02:47]
But nonetheless it is something to always that's kind of fun to think about that you can use these algorithms in really unique ways that actually become super useful. And I'm sure that taught me something that I've used throughout my life. I want to end on a positive note somewhere, right, it was great.

[00:03:02]
All right, we got 13th which means we lost in the finals right away. All right, so we went over the running time, somewhere of n login all the way up to n squared, depending, right. And of course, next we're going to implement quicksort. Hey, did you know that I teach a course on Vim?

[00:03:18]
This sweet editor that I'm using that super fast and super cool, and it goes really, really, really fast and all these great things. Yes, so if you're ever curious I do a developer productivity which allows for sweet, this and vim usage and all the great stuff, fantastic. Okay, anyways, back to it.

[00:03:33]
You have to sell your own course, it's just a part of things. All right, so let's do quick sort. So this is the test for quick sort. I have a debugger here, cuz obviously I've gotten it wrong multiple times in my life. So this is the array we're going to sort.

[00:03:48]
And hopefully we can sort this. So let's just jump to it and now it's the sorting time. So we get an array and we're expected to sort. So there's two functions that we really need to think about if we replay what I talked about there was this whole like, running these two things side, right?

[00:04:09]
But there's also this whole pivoting side. So often when you see quicksort it's split into two functions. There is something referred to as the partition, I think that's how you spell it. Which actually produces the pivot index and moves the items that are less than or equal to on one side and the items that are greater to on the other side.

[00:04:30]
Then the second thing is your actual quicksort, which does the quick sorting which calls partition gets the pivot, then recalls quicksort does the recursive step and the base case step and does all of the kinda the bookkeeping. So we usually break it up into two different functions. So let's start here and let's just create a function we're gonna call quick_sort, right?

[00:04:51]
So I'm just gonna call qs, quick_sort, make it easy. Pass in the array, and then we need to pass in the low and the high. So the high, remember, what did I say specifically about the high? I think I said it right on the screen too. Did I say it on the screen?

[00:05:05]
Yes, I did, right there. It's inclusive. A very unusual thing you do. In most algorithms you don't do that. So let's do R dot length minus 1 minus smiley face minus 1. There we go. So now we just need to program two functions, the quick_sort function, again, the recursion function and then the partition function, how we get the index.

[00:05:25]
So just to make TypeScript not give me a bunch of errors let's go quicksort arr number array low number high number and what do we need to return out? Well, if we really wanted to we could just return back out the array to make it super simple. We don't have to do that, you can do that.

[00:05:43]
This one doesn't actually need the array right here, so we don't need to do that. Void, awesome, so we have that one done and then we need one more. We need the function partition, right, partition, right here, which is gonna take in the array, the low, and the high cuz remember, this thing needs to be able to run on all these little spots in here, right?

[00:06:05]
It needs to be able to run, on one through seven, so we need to be able to give it hey, you're running from low one, high seven, right? We have to be able to do all these things. So we have that right here, and it needs to return back out.

[00:06:21]
What is the pivot index? Where did we end up splitting the array to? Where did we weekly sort this array? Awesome. So which one do we wanna start with? Should we start with quicksort or should we start with the partition? I'll let you guys decide.
>> Partition.
>> I love that, someone had an opinion.

[00:06:44]
All right, so let's start with the partition. So the partition shouldn't be too hard, we'll just do the easy way which is I'm going to create a pivot, which is gonna be simply the array at the high position. I know this could cause that whole sorting reverse sorting super duper issue, but let's just have an easy time with this.

[00:07:00]
We don't need to do anything super fancy. Then at this point I'm gonna create an index. This is where so, most books will actually create it at negative one. You'll see why they do it in this specific way. You don't have to do it this way, you'll just see most pseudocode, I'm pretty sure if I went to Wikipedia right now, it would actually say that, start at negative one.

[00:07:17]
So at this point, we have to walk from the low to the high, but not including the high because the high is the pivot. So we just have to now do a weak sort on this subarray. So let's do the weak sort now. So, for let i = lo, i has to be less than hi, + + i.

[00:07:39]
Now what are we comparing it to? Remember each element needs to be compared to the pivot, not like i plus one, not something adjacent to the pivot. So if Array i is less than or equal to the pivot, we now need to put that value into the first slot or the second slot or the third slot or however many slots we need to put it into to make this into a weakly sorted array.

[00:08:08]
So we'll go like this const temp equals array i. Forgot this, so in the most pseudocode you'll find that they first increment the index at this point, that is now we're now into the zeroeth position. We went from negative one to the zeroeth position which I've also done something wrong here.

[00:08:27]
We gotta go to low minus one, right? Cuz we have to be able to put it into, where is this? We need to be able to put stuff into the ninth position or into the, whatever position. Remember, cuz we're doing these little sub sorts on these different spots within the array.

[00:08:46]
Always forget to do that. That's one of the ones that got me multiple times. That's why that debugger message was there. Forgot to put or take advantage of using low. So low minus one, so right now we're off of it. The moment we find something we need to swap, we move it into the first position, now we do the flop.

[00:09:02]
We're gonna go array i is now going to need to be swapped with array index or array i equals array index, array index equals what is it? Temp there we go. Swapping, swapping I don't know why it's always so hard, I always mess it up. It's just the worst.

[00:09:23]
So there we go, it's as simple as that. We've now found everything and moved it over into the beginning of the array that is less than our pivot, but we have one problem left. What is the one problem left? Let me tell you, let's see if we can do this, here, I'll do this.

[00:09:45]
So I really want this one to sink in. I feel like quicksort is just such a great algorithm. I just really want to make sure that people really get this one. Which is let's just say we had an array of 1, 7, 6. I didn't plan on doing this so hopefully this all works out swell like.

[00:10:00]
And let's go with 5, all right, fantastic, let's go with 8 on this side, perfect. It's gonna be a pretty poor sort but we're gonna do it. So we pick 5 as our pivot and we start off with index that's here off the thing right, so we first check here is this less than 5?

[00:10:20]
No, it's not, though you are a crooked 8 it's not less than 5. Is this less than 5? No it's not. Is this less than 5? No it's not. Is this less than 5? It is less than 5. So let's move our index to right here, now pointing at this, and we are going to swap you for you.

[00:10:36]
Awesome and we're gonna go up and to this point, but not including the fifth one, cuz the fifth one or, that one is that the fifth one? It also happens to be the fifth one or the index four right there. So there we go, we've now flopped it, everything's good.

[00:10:49]
So our array looks like this 4, 7, 6, 8, 5, 5 being our pivot. So what's the last thing we have to do? We have to put our pivot where the pivot index is, right? So that way we hold true to the one rule which is everything to the left of the pivot needs to be less than or equal to, and everything right of it needs to be greater than it.

[00:11:17]
So we're gonna have to do one last swap right here. So let's go back down here and we go index plus plus, increment it once more. So, if we found nothing less than us, we've incremented into a position of 0 or low at this point. So we do that and now we're gonna go arr[hi] = arr[idx] and arr[idx] = pivot.

[00:11:41]
We already have the temporary specified right up there, right? So I didn't need to create the temporary variable in the swap. There we go. And the last thing we need to do, of course, is return the pivot index right here. Fantastic, we've done it. We've written the pivot algorithm.

[00:11:55]
Was that kinda hard? Was that a lot to take in? Or hopefully these explanations, these things make it a little bit easier to kind of walk through and follow this, which is fantastic, all right. So let's go up to QuickSort, and now we just need to do the QuickSort side of things.

[00:12:09]
So what's our base case? Well, when we get to the point where low and high meet, all right. So that is a bad time, if low equals or is greater than or equal to high, I always put greater than, even though I don't think that can ever happen.

[00:12:23]
It just makes me feel like it's, I just catch all the possible conditions. I don't know why I do that. It just feels good, you know what I mean? So once this happens, we have now officially stopped needing to recurse. We've ended the line, so let's return, fantastic.

[00:12:40]
If we don't hit that, we need to do three things. First, we need our pivot index, right, whoopsies, which is gonna be partition and we need to pass in the array, the low and the high, right? So this thing is gonna do the weak sort. It's gonna set the pivot into the correct spot then return the pivots index.

[00:12:58]
So now, we need to just repeat this again but we need to make sure we don't include the pivot index on our repeat. So, quicksort array, lo, to pivot index -1. Right, because remember, it's inclusive endings, not exclusive endings. So if we didn't have that right here, we'd have to do some math to make it all work out.

[00:13:21]
We'd have to put plus ones and minus ones elsewhere. So we don't have to do that. We do have a question.
>> I use 5 as a pivot.
>> In this case, all I did was pick the last element. So I wanted to make it identical to the algorithm that I did.

[00:13:35]
Which I just simply pick the last element, I didn't pick 5 as a good choice. I just picked it as the choice I programmed All right, then of course remember, we need to go to the pivot and beyond one. I think I just quoted Buzz there for a second.

[00:13:57]
And then we're gonna go up to the high. So now notice what we've did, we're gonna repeat the quicksort on one side of the array, on the other side of the array, but we're not including the pivot. Does this make sense? Everything's looking good, now, I'm sure there's an over and under going right now, but do we feel like I've gotten this, first try?

[00:14:19]
Okay, we have just, people are out there saying absolutely. All right quicksort so we're gonna run this and I get this one. Look at that, we got it. There we go. So we got that first try, just knew it. Complete confidence there for a second. So there we go, so that is all quicksort is.

[00:14:40]
It's just a simple partitioning and repeat, this is a divide and conquer strategy. I find this one to be really, really awesome, easy, it's much easier to program than Merge Sort. Merge Sort, though often used, is very, very complicated in my book. So I like this one, fantastic.

[00:14:58]
And at that point, we did it, we're kind of done with lists. There's no more lists, we're gonna be done, we're fully done. But technically in a sense lists are actually our trees in some sense, they're very, very similar, so we're not really done, we're just kind of done, right?

[00:15:19]
You're gonna have a whole load of node like opportunities coming up and we're gonna use a ton of recursion. So if you're not familiar or if you felt like your recursion chops weren't quite up to snuff, you might want to take a moment. And so all programming eventually leads to trees.

[00:15:34]
This is just a fact of life. The Falkor thing that I mentioned where I could have ruined all of Netflix, that was just a tree. Well, it was actually a forest which is a series of trees that were also pointing to other trees. It was like a graph that was also a set of trees.

[00:15:46]
It was very confusing, I can't quite tell what it was. It was a linked list and a tree and a graph all at the same time, just depends on how you looked at it.