Transcript from the "Review: Quick Sort Part 1" Lesson
>> Bianca Gandolfo: So quick sort is another recursive divide and conquer sorting algorithm. So we have our divide and conquer steps here. Of course we need to recognize our base case. What happens if we don't recognize our base case?
>> Speaker 2: Infinite loop.
>> Bianca Gandolfo: Fun forever until your browser crashes, right, infinite loop.
[00:00:16] One, I guess zero one, one is we're going to divide And two we're gonna conquer, so divide and conquer for the quick sort is in the same step, it's our partition step. And then combine, we don't really have a combine in this case.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: All right, let's talk about the partition.
[00:00:40] So the goal is to move the pivot to its sorted place in the array. So a key here is a pivot is a number that you choose. In this case, we're choosing five, we're just putting it at the end and we're gonna keep it highlighted so we know.
[00:00:56] We want know to In this case, we're just getting it out of the way. But eventually, if we have all of the lesser values, which are these blue values, to the left, and all of the greater values to the right, then we know that 5 is in its final location, right?
[00:01:15] Everything else is still unsorted, but 5 is good, so that is our goal. Is to get 5 into it's final location by moving through the array. Moving all the lesser one's to the left, and keeping track of where. The lesser values are to the left of. So right here, the lesser values are our past to the left of 1, right, index 1.
[00:01:47] Here the lesser values are to the left of index 0, 1, 2, 3, etc. And so, we keep track of it, and that is what we call our pivot location. So as we're adding lesser values, our pivot location is moving to the right. We start a pivot location at the beginning, and we say, is 3 less than 5.
[00:02:14] Yes, so we move our pivot location over, is 7 less than 5? No, keep a pivot location the same. 8 less than 5? No, keep the pivot location the same. 4? Less than 5? Yes, move 4 to the pivot location, right, which is 1, keep moving. All right, then swap them.
[00:02:38] 2 same thing, swap it so now pivot location is here. Cool on that process? And again the idea is we want all the lesser values, these blue values to be to the left of our pivot. Which is 5, which is just a number we randomly pick. Sometimes we'll pick the one at the end, sometimes we'll pick one in the middle, sometimes it's a random number depending on the implementation, and how you expect your data to come into your algorithm.
>> Bianca Gandolfo: Cool, we saw a couple different ways of doing it, was that yesterday or two days ago? One was to swap or pivot, twice right? So, as we moved up we swapped our pivot and then we swapped it back, and then another way that we saw, was we kept the pivot at the end and just swapped it.
[00:03:36] In our very last,
>> Bianca Gandolfo: Once our pivot location had completed, it's round, right? Once we've gone through and made sure all of the elements that were lesser were to the left and all the elements that were greater were to the right. Which is essentially you just have to loop through the entire array.
[00:03:58] Except for the last one. Array.length- 2, cool. Can I see thumbs on that? Could I get a question around this partition step?
>> Speaker 2: Whenever we implemented it, we grabbed the one from the end.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 2: Does the implementation change much if you grabbed one from is it the middle?
>> Bianca Gandolfo: Not really.
>> Speaker 2: Not really?
>> Bianca Gandolfo: Not really, I mean the reason that there is all kinds of theory around which one you should chose. If you know that it's not a sorted array or like mostly sorted. Then it's fine to just chose the end. But if you think it's gonna be mostly sorted, well you shouldn't be using quick sort.
[00:04:45] But then picking one in the middle might make it less likely that it's the maximum value, right? So if you pick the maximum value every time, this step of swapping is gonna become exponential time. Cuz when you break it up, you're going to have nothing going to the right, everything going to the left, and then it's just a quadratic algorithm at that point.
[00:05:16] So that's why where you pick is important as long as you're not picking the maximum.
>> Speaker 2: How many total different ways actually do you do this? Another new way, so that we have [CROSSTALK]
>> Bianca Gandolfo: We just have two ways, this is the same way that we looked at in our, well this is a little bit different.
>> Speaker 2: Different?
>> Bianca Gandolfo: Because we're choosing the one in the middle [CROSSTALK]
>> Speaker 2: Mm-hm.
>> Bianca Gandolfo: There're a bunch of different ways of doing it, yeah. So we chose the one in the middle this time The last two times we always chose one at the end but it's not different other than that.
>> Speaker 2: But and this was the double spot right?
>> Bianca Gandolfo: No, this was the same as well.
>> Speaker 2: Is it?
>> Bianca Gandolfo: Yeah, cuz we just move it to the end and once we're done.
>> Speaker 2: I see, I was looking at the two arrows.
>> Bianca Gandolfo: Yep.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yep.
>> Speaker 2: You said something about array.length minus two.
>> Bianca Gandolfo: Yep.
>> Speaker 2: What was that?
>> Bianca Gandolfo: So we'll loop up to the second to last.
>> Speaker 2: Okay, okay.
>> Bianca Gandolfo: At the time, cuz our pivot is at the end, yeah.
>> Speaker 2: I wonder if, would it be practical to have chose the median as the pivot.
[00:06:24] Cuz I think you can find the median and I'll log in.
>> Bianca Gandolfo: Just maybe choose three and then choose the one in the middle?
>> Bianca Gandolfo: Or just loop through?
>> Speaker 2: Well I choose the median value so that the splits would be equal.
>> Bianca Gandolfo: Yeah, yeah, if, depending that would be another linear time operation.
[00:06:47] And if you can handle it, and there's a chance that it's mostly sorted of something like that, it might be worth it, for sure. Cool.
>> Speaker 3: Got a question from online.
>> Bianca Gandolfo: Yeah, can you please explain this example again, with pivot = 5? Sure, so our first step is to choose a pivot point.
[00:07:12] In this case, we're choosing just this random pivot point, yeah? And we're gonna move it to the end just so it's out of the way. Cool, so we switch five with four just to get the five our pivot point out of the way, cool? So we start at the beginning with our pivot location being zero.
[00:07:33] And again, the goal is that we wanna make sure all of the items to the left of our pivot point are less than our pivot 5, tight? And that is shown as
>> Bianca Gandolfo: The blue ones, right? So we're gonna start here. At this point our pivot point at the very, very beginning, our pivot point is 0.
[00:07:56] We say is 3 less than 5, so if the element is less than or equal to the pivot We are going to,
>> Bianca Gandolfo: We're going to make sure this element is before the pivot location. So here we go, we're just gonna move the pivot location up one. So now a pivot location is one, right.
[00:08:24] We didn't need to swap anything at this point cuz it's just at the beginning, all right. Does that make sense? Cuz we're already at the pivotal location. So now it's one, let me check is 7 less than 5? And we're checking all of them right whether the pivotal location is here, here, here.
[00:08:42] We're gonna loop through all of them to check and swap them. So if your location is 1, is it less than? No, so we're gonna move forward, the pivot location is still the same place, okay? So is 8 less than 5? No, we're gonna keep moving. Again, the pivot location has not changed.
[00:09:01] Now, we say is 4 less than 5? Yes. Now, we are going to switch 4 with the pivot location.
>> Bianca Gandolfo: And increment the pivot location by 1, which is now 8. However, we're still gonna check 2 next.
>> Bianca Gandolfo: Okay? So is 2 Less than 5? Yes, so we're gonna switch 2 with the pivot location, here, and increment the pivot location by 1.
[00:09:35] The next one, so the pivot location's here, and we're gonna check our next one. 1 is less, so we're going to move it to the pivot location, increment the pivot location by one. The next one we're looking at is 9. 9 is not less, so we leave it alone.
[00:09:55] We don't increment the pivot location. We go to the next one. 5, is 5 less than or equal to 5. Yes? We move it to the pivot location, increment the pivot location by one, and then we loop through the entire array at that point. And now you can see the pivot location is here.
[00:10:23] All the elements to the left are unsorted, but less. All the elements to the right are unsorted, but greater. And so what we need to do is move phi to the pivot location which is it's final point, where it needs to be. And it's not gonna move after this, this is where it's gonna be.
[00:10:44] And the recursion happens after this, where we then partition the left, and we partition the right. And with each recursive call, our elements will wind up in their final place. Just like 5 through the partitioning. This is the partition step wound up in its final place. So you can imagine, as this breaks down further and further, we have our elements landing in their final place, right?
[00:11:18] And we know it's the final place because anything that's less than the pivot Will be to the left, and anything that's greater will be to the right, always, and that's the final place. Whether or not on either side of it is sorted at that point.
>> Bianca Gandolfo: That make sense?
>> Bianca Gandolfo: Okay, I have a question from Miranda.
>> Miranda: No, I think I got it.
>> Bianca Gandolfo: You got it?
>> Miranda: Yeah.
>> Bianca Gandolfo: What was the aha moment for you?
>> Speaker 3: Like, what was something that wasn't clear that is now more clear?
>> Miranda: I think visualizing going through the array,
>> Miranda: With the same pivot location, I think that's where I was stuck.
>> Bianca Gandolfo: Yeah, so the fact that the pivot location only changes when? When it's less than, yeah.
>> Miranda: Less than, yep. I don't think I grasped that. [LAUGH]
>> Bianca Gandolfo: Yeah, yeah and that's an important point, cool it wasn't clear for me at the beginning while we were tracking pivot and pivot locations separately.
>> Speaker 2: Because I didn't get that it was a final pivot location, I thought that we were moving the pivot and then for some reason scoring the location separately. Yeah yeah, I've been brainstorming on what can we name these, the pivot and pivot location To make it more clear?
>> Miranda: I think maybe that's why it's confusing, cuz they're so similar, I don't know.
>> Bianca Gandolfo: Yeah.
>> Miranda: I think I got it. [LAUGH]
>> Bianca Gandolfo: Yeah.
>> Speaker 2: Just calling it final pivot location works, I think?
>> Bianca Gandolfo: Yeah, final pivot location. Yeah, so my only issue with that is that then it's kind of saying, maybe like potential final tentative location, because its not actually final until it's final, right?
[00:13:19] So, yeah I was thinking about that and was like that may be misleading.
>> Bianca Gandolfo: Potential final pivot location