Transcript from the "Understanding the Quick Sort Partition" Lesson

[00:00:00]

>> Bianca Gandolfo: Let's talk about the partition. So there's two main parts of the partition, there's the pivot point which is the element that we choose at the end. And then there's the pivot location which is where that, the four wound up in it's final resting place and that's sorted.

[00:00:20] So that is the core of the partition step.

>> Bianca Gandolfo: Cool, can someone take a stab at re-explaining to me what exactly is happening in the partition?

>> Speaker 2: So you pick an element from your list. And then you sort what's left of it into greater and smaller than that element.

[00:00:53] And the pivot point moves to its correct location in the sort. Everything else is only sorted so far as if it's larger than the pivot point, it's on the right, if it's smaller, it's on the left?

>> Bianca Gandolfo: Yep, exactly, cool. Can I have,

>> Bianca Gandolfo: One and a half clarifying questions from the audience?

[00:01:25]

>> Bianca Gandolfo: So I have questions pretty easy. It's like a question that you might already know the answer to. Sure.

>> Speaker 3: What's a pivot?

>> Bianca Gandolfo: What is a pivot? The pivot itself you can think of as a swap, yeah.

>> Speaker 2: So theoretically it could be anything, right, you can?

[00:01:44]

>> Bianca Gandolfo: Like the pivot point?

>> Speaker 2: Yeah.

>> Bianca Gandolfo: Yeah, you can choose anything, there's all kinds of theories about which one to choose, which one is better, depends if you're

>> Speaker 2: But in this case, you've picked the last one?

>> Bianca Gandolfo: The last one, yeah, yeah. Last one, the first one, it's usually a sort of entry level quick sort and it works fine.

[00:02:03] Unless your list is mostly sorted or completely sorted already. In which case, that's like the worst thing that you could possibly do. Hopefully you would know if your list is already sorted though. And you probably wouldn't choose a quick sort. You actually wouldn't need to sort it at all, no sorting, cool.

[00:02:24] So that's a partition, so that's where the action is happening, right? In the merge the action is happening when you're combining it, in the quick sort the action happens in the partition. Okay, we're gonna keep going, cool. So here's our goal, we wanna move the pivot to its sorted place in the array.

[00:02:45] So we choose a pivot point, it's usually gonna be the last element. But again, we have all kinds of debates around that. So we start the pivot location at the beginning, iterate through the array, and swap them so that the larger ones are to the right and the ones on the left you just keep them to the left.

[00:03:04]

>> Speaker 4: Can you say that again?

>> Bianca Gandolfo: Sure. So, we choose the last element, that was our 4. We start at the beginning of our array, and we loop through and compare them. And if one is larger, you basically move, you like move it over.

>> Speaker 4: And that one goes to the end or?

[00:03:36]

>> Bianca Gandolfo: It can, it depends on the implementation. But basically the way you want the pivot to move over one, so there's one to the left of it, immediately, so you have to choose what you're gonna do with that one. Whether you put it in the first place might be the easiest one, but there are other ways to do it as well.

[00:03:56] And then you wanna make sure that whatever's greater is on the right. Because it's going to be kind of inching it's way. And I can show you the picture. So you see how the 4 is inching its way. It goes to the left one each time. And in this implementation, we're just swapping it.

[00:04:16] So, when 3 is less, so we keep it there. 7 is greater, so we move it to the last one. However, we don't want 4 to be in 7's place, we want it to be one over, so we swap the 4 with the 5.

>> Speaker 5: So how does the 7 get placed to the right of the flow, does it create a slot, move 7 and then delete that?

[00:04:41]

>> Bianca Gandolfo: So we don't create the slot, so the slot already exists. So what you need to do is you need to move the 7 where the 4 is. You probably have to save a value outside while you're swapping, right? Swap it, and then make sure you move the 4 over one to the left and swap it with the 5.

[00:04:58] Does that make sense? So your 4 should only move over one to the left each time.

>> Speaker 5: So it's kind of like swapping out?

>> Bianca Gandolfo: Yeah. And I know these arrows are a little bit confusing.

>> Bianca Gandolfo: But,

>> Bianca Gandolfo: I know, it's kind of one of those brain hurty things.

[00:05:18]

>> Speaker 5: How do you choose you choose 4 and how do you choose the other element? It's randomly or just you?

>> Bianca Gandolfo: You start at the beginning.

>> Bianca Gandolfo: Yeah, so you start, so 4 is your pivot point that you want to end up in its final place, right? And we know that it's in its final place when everything that's less is to the left, and everything to the right is greater.

[00:05:49] And so we wanna pivot or swap all of our other,

>> Bianca Gandolfo: Elements to be in the right place.

>> Speaker 5: Yeah, my question is, just to be, we choose us as the pivot we worked for? And how do we choose the other element to swap, now we see that we are swapping 7 and 5?.

[00:06:15] What if we, instead of that, we use 8 or 9 as a beginning? Is there anything, is randomly, or just you choose?

>> Bianca Gandolfo: So the easiest way to do it is to have your pivot point B at the last, the end, and then start your iteration from the beginning.

[00:06:34] But there's lots of debate over the specifics around that. But this implementation and the one that we're gonna do in the exercise is going to recommend that you start at the back and then you iterate from the beginning and compare.

>> Speaker 6: So you're shifting like three numbers around until you get to the end?

[00:06:57]

>> Bianca Gandolfo: Yeah.

>> Speaker 6: There's a 5 in the wrong

>> Bianca Gandolfo: So we do one more.

>> Speaker 6: So you're just trying to get all the small things on one side and all the big things on the other side?

>> Bianca Gandolfo: Yep.

>> Speaker 6: And that's it.

>> Bianca Gandolfo: But why, why?

>> Speaker 6: Because then you have the smaller set to sort on each side of it?

[00:07:21]

>> Bianca Gandolfo: That's true. But also, if everything on the left of the pivot location is smaller, and everything to the right of the pivot location is greater, you know that that number, 4, is in it's final place. You know, you don't need to move it anymore.

>> Speaker 6: Okay, you don't need to move the 4 any more.

[00:07:38] That makes sense.

>> Bianca Gandolfo: And also, now we have two smaller things to work with in which we're gonna do the same thing recursively. Which that's kinda where the mind goes whoa so many. But that's the basic process.

>> Speaker 5: Kindly explain the arrow, just you moved 4, and why you moved 5 to-

[00:07:59]

>> Bianca Gandolfo: Yeah.

>> Speaker 5: Yeah, you moved 7 to place of 4?

>> Bianca Gandolfo: Totally, yeah.

>> Speaker 5: So I think you see number 3 is less than 4, and go to 7. 7 is greater than, you move 7 to the right. Why you jump to 5 to take to them 7 place next?

[00:08:22]

>> Bianca Gandolfo: So your question is, why don't we just switch 4 and 7 and then just keep 5 where it is?

>> Speaker 5: No, if you start from the beginning, 3 is less than 4, and you jump to 7, you swap 7 to the right side of 4. And the arrow shows 5 is taking to place of 7, why?

[00:08:47] So instead of being that leaving 5 right there and go to the next to 7, that is 8. Like that, why you start at 7 and jump to 5 in the likes?

>> Bianca Gandolfo: Yeah, so the question is why are we even messing with 5? Is that putting it out of order and doing something weird?

[00:09:10] The answer is not really. So when we add 7 to the end, we're not just tacking it to the end, what we're actually doing is we are swapping 7 with 4. So see the first thing that happens is this bottom arrow. We say 7 with 4, right? So now 4 is over here, which is what we don't want.

[00:09:33] We want to make sure that 4 actually goes to the proper place. We want 4 to only move to the left once each time. We don't want to mix 4 up. 4 is in a special place. We wanna make sure that it's consistent and that we don't lose track of it.

[00:09:51] So we move 7 over, we move 4 to the next left and then whatever is in that spot is gonna be swapped with 7. And the specific order in which you to do that is up to you, but those are the three things you wanna do.

>> Speaker 6: What if you just happen to select the largest number as your partition and it was already to the right most place?

[00:10:15]

>> Bianca Gandolfo: What do you think happens?

>> Speaker 6: And it would get nowhere. Well, I mean, it would recurse, right? So then you would just partition the next section.

>> Bianca Gandolfo: Yeah, what if you got the largest one every single time?

>> Speaker 6: It would not be very fast.

>> Bianca Gandolfo: Yeah, right?

[00:10:31]

>> Speaker 6: And I mean, that's what I'm thinking of. But you would have to have somewhat to do that. [LAUGH]

>> Bianca Gandolfo: Yeah and that's the argument behind it, it's like yeah quick sort in the worst case is n squared. Absolutely. Totally terrible. However, the chances of it happening are pretty low.

[00:10:50] And there's lots of mathematically proofs that are beyond the scope of my knowledge. But you're welcome to, if you're into that, look it up. I'm gonna answer some questions here.

>> Speaker 7: That would mean your list is already sorted, right? If every time the last one was the biggest one.

[00:11:06]

>> Bianca Gandolfo: Yep, yep yep, exactly. So why is it called quick sort and not partition sort? That is a great question. We can make a movement and call it partition sort, make it really clear. Quick sort is the most popular sort, and it's considered the fastest, so we call it quick dort I think.

[00:11:23] I don't know the history of the name, but I'm gonna go with that. So, Brett ask, so, we're comparing 4 and 7 the first time? The very very first time we're actually comparing 3 with 4 and we're like, well, actually that's smaller, BS. And then the next time that we actually care about when a swap happens is the 7 and the 4.

[00:11:43] So yes, that's true in Brett, calling people like numbers now. [LAUGH] Okay, how are we feeling about this?

>> Bianca Gandolfo: Are we closer in our minds, in our hearts, in our souls, and all those parts of ourselves?