Transcript from the "Review: Quick Sort Part 2" Lesson
>> Bianca Gandolfo: Here is our code for the partition. So it's gonna take an array, and a low and a high. If it we're doing the whole array, like we did before, where just the, we're just gonna choose the last one, right. It's a little bit different than this example where we choose five, we're just gonna choose the last one.
[00:00:18] So in our example, we would just choose four, just out of simplicity. And then our previous location is gonna be the beginning, right. So it's low and the reason we passed this every time is because as we're doing recursion, the high and low are gonna change. The arrays are gonna stay the same.
[00:00:35] This is an in-place sort. But the part of the array that we're looking at is gonna be smaller every time, hopefully, right, if we're doing it right. So again, our pivot, we're just gonna choose the last one. Pivot location is gonna start at the beginning. So, the first time will be four and this one would be zero, right.
[00:01:00] We just start at the beginning of the array. This is gonna be the end of the array. So we're gonna iterate through the entire array. And if the element that we're looking at, right, we'll start at the beginning. We're gonna loop through the entire array. Is less than or equal to the pivot.
[00:01:20] You're going to swap it with the pivot location. And then we're going to increment the pivot location, when it's less. Cool? Otherwise you do nothing. And you're going to keep doing that. You're going to keep swapping all the lesser items to before the pivot location, and incrementing the pivot location whenever it's less.
[00:01:43] And then at the end, you're just going to swap the pivot itself to its final pivot location. Here, this pivot location is just a potential final pivot location until we have looped through everything, and then we swap it. Cool? Awesome. And here is the entire thing. So here we're initializing our low and high.
[00:02:16] We're gonna loop through from low to high, we're gonna partition. This is going to return the the pivot location for us, so we know the next left and right we want to work with. And so you can see here, we referenced that pivot location to again, recursively, partition the left and the right side.
>> Bianca Gandolfo: Cool.
>> off screen: So if I was in an interview and somebody asked not to whiteboard it or anything, but to just put into words why Quicksort is more efficient than, like I don't know, Bubblesort, or something like that? What would be, I mean I could say like, cuz it's in log n but like.
[00:03:08] Do you know what I mean? Is there a good way to put into words what-
>> Bianca Gandolfo: Why it's probably faster?
>> off screen: Yeah.
>> Bianca Gandolfo: So in it's worst case it's actually not faster. It actually is n squared in its worst case but that's very, very unlikely and has been proven to be so unlikely that it is kind of not worth worrying about.
[00:03:31] But, the reason it's n log n, would that be a better answer to your question? Why is it n log n? Is that what you're asking? Okay. So what makes it n log n? So what makes it n, right, is the fact that we're looping through the entire array, right.
[00:03:55] We have to loop through the entire array. That's in, and the part that makes it log n is the slicing it in half, and recursing, right?
>> Bianca Gandolfo: And so, every time you recurse, you continue to slice it in half, but you always have to loop through the entire thing.
[00:04:15] So that's n times log n. So if you were just recursing, and you weren't having to loop through the entire array, it would just be log n. But since we have a linear time operation inside the recursion, or the recursion's actually inside the other one, we have to multiply them, and it's n log n.
[00:04:33] And the reason you were asking a couple days ago, or yesterday, whenever that was, was why, why is it n log n and not n or whatever? We talk about cutting significant digits, what makes it significant?
>> Bianca Gandolfo: It's just significant, the n and the log n are both significant.
>> off screen: Both significant?
>> Bianca Gandolfo: Yeah, because it shows that it's slower than linear time, but it's not quite exponential. Yeah.
>> off screen: Okay, thank you.
>> Bianca Gandolfo: Yeah, cool. All right, let's reflect. This was a fun one.
>> Bianca Gandolfo: So we said before, that remember the pivot location, oops, only changes when the element is less than the pivot, right.
[00:05:42] So that was a thing.
>> off screen: And also,
>> off screen: You only swap the pivot when you're done comparing all of the others.
>> Bianca Gandolfo: Yeah, so one way you can swap the pivot to the final pivot location at the end, yeah.
>> Bianca Gandolfo: Cool, what else?
>> Bianca Gandolfo: What's something that's still a little fuzzy?
>> off screen: Think it might help, like the partitioning portion of the sorting, there's different ways to do that. Maybe you can have different methods like comparison and contrasting, kind of like a table or some kind of visualization, like summarizing all the different ways you can do the partitioning
>> Bianca Gandolfo: Yeah, absolutely.
[00:06:44] Contrast, contract. Contract that partition, that sounds dangerous. Yeah, so, the big takeaway here is that it doesn't really matter specifically how you get there, as long as you somehow get all of the items that are less than the pivot to the left and everything that's greater to the right.
[00:07:09] Specifically, how many swaps you get there really doesn't matter, or which element that you choose for the partition, for the most part doesn't really matter. People have all kind of theories and write research on this but for our use case, you just have to pick a pivot and make sure everything to the left is less, everything to the right is greater and how you get there is up to you.
[00:07:34] Yeah, and there are different kinds. There's different ways of getting there.
>> off screen: Yeah, even like the first time you did We kind of like tap the pivot and the location and in the first swap, you could do like in two different arrays.
>> Bianca Gandolfo: Yeah, yeah, yeah, yeah.
>> off screen: So like the first fork in the length minus one, with the pivot location and then you do the pivot and like so it's kind of.- Yeah, yeah, yeah
>> Bianca Gandolfo: Yeah there's a few different ways you can do it and it can be kinda confusing. Yeah, I get that, cool. Thank you.
>> Bianca Gandolfo: Did anyone code this out all the way?
>> Bianca Gandolfo: No? Couple people, yeah.
>> off screen: I worked on it, but I had to look at the solution.
>> Bianca Gandolfo: You looked at the solution? Cool. So did you look at the solution and then go back? And were you able to do it?
>> off screen: Yeah, I mean I tried on my own for a while. And I failed, and I looked at the solution and went back and saw what I did.
>> Bianca Gandolfo: Yeah, totally. Yeah the first time I did Quicksort, I had to look at the solution too. Yeah, that's kind of a, it's pretty abstract, it's not a straightforward concept. Who here thinks that if they needed to implement Quicksort now, in a non pressure interview situation, that they could do it?
[00:09:08] Okay, and we're just hanging out eating pizza and coding up Quicksort, cuz you know, it's Saturday night and that's what we do. You don't do that on a Saturday, no, okay.
>> off screen: I think if I could run it and then when it didn't work, change some things a few times.
[00:09:23] I think I could get it going.
>> Bianca Gandolfo: Cool, so if you could debug it?
>> off screen: Yeah.
>> Bianca Gandolfo: If you're not whiteboarding it, essentially?
>> off screen: Yeah.
>> Bianca Gandolfo: Got it, okay, cool. Anything else? Jen, do you have any thoughts on Quicksort?
>> off screen: That's kind of the same. [LAUGH]
>> Bianca Gandolfo: Yeah, so if you could debug it, you feel like you could get there, but maybe on the whiteboard, not so much?
[00:09:46] Cool, that's fair, awesome. Yeah, attempt this in your interviews with caution. Definitely try to master it before trying to show off and be cool. Just start with Bubblesort, if you need to. But just remember these facts, and bring them up, you're like, there's Mergesort and Quicksort. I know they'd be faster, but let's start with a naive approach and just go from there.
[00:10:09] Make your life easier.
>> Bianca Gandolfo: Cool, there's some more Quicksorts for further study if you're interested