Transcript from the "Pseudocoding Quick Sort Part 1" Lesson

[00:00:00]

>> Bianca Gandolfo: So here's our Pseudocode for the partition. So we have the list. We have a low, right? And we have the high. So we wanna choose the last element as the pivot. Then we wanna keep track of the pivot location, which is initialized as low. Okay, which is initialized as the very first one, which is low.

[00:00:25] And then you're gonna loop from low to high. Which is from zero to array dot length.

>> Bianca Gandolfo: And if, the current element is less than or equal to the pivot you're gonna swap it. You're gonna swap the pivot location in I and then you're gonna increment the pivot location.

[00:00:48] Does that make sense? Let me think about that. So if I is less than the pivot, swap the pivot. We wanna swap the pivot.

>> Speaker 2: There are two swaps in the other drawing.

>> [INAUDIBLE]

>> Bianca Gandolfo: Yeah, this is just a partition.

>> Bianca Gandolfo: Or are we missing something?

>> Speaker 3: You just move the pivot.

[00:01:25]

>> Bianca Gandolfo: Let's see. Choose last element as the pivot, so this is our form, remember?

>> Speaker 2: Mm hm.

>> Bianca Gandolfo: This is gonna be zero. Array at zero, remember this one was, what was it at first? It was 3, remember that? If 3 is less than or equal to the pivot, swap pivot location in i.

[00:01:52] So pivot location was the length.

>> Bianca Gandolfo: And then i was 0. Okay, increment pivot location to 1. That's not quite landing with me.

>> Speaker 4: Is that right?

>> Bianca Gandolfo: Doesn't appear to be right. So what's wrong? What's broken?

>> [INAUDIBLE]

>> Bianca Gandolfo: So what do we say? We chose the last element as a pivot, which we can think of as our array.

[00:02:31]

>> Bianca Gandolfo: Let me make this more readable. Make it big, look at that. Yeah.

>> Bianca Gandolfo: Okay, all right.

>> Bianca Gandolfo: Okay.

>> Bianca Gandolfo: Okay, so we're gonna choose the last element as pivot. So what was that? Like our array.

>> Bianca Gandolfo: Yeah, which was 4 in our example. You guys remember the numbers?

[00:03:12] So we're gonna keep track of the index for the pivot location which we're gonna start at 0

>> Bianca Gandolfo: 0.

>> Bianca Gandolfo: Cuz we start at the beginning. So for I, we're gonna loop from 0 to array.length. If array at i, so first one is 3, is less than or equal to the pivot, which is 4.

[00:03:42] It's gonna be true, right? We swap the pivot location and i. Hm, what does that do?

>> Speaker 2: Aren't they both zero right now?

>> Speaker 3: Wouldn't it move the four, wait, what is i?

>> Speaker 2: Pivot location zero, I assumed i started at zero.

>> Bianca Gandolfo: Yep.

>> Speaker 2: So nothing. Zero and zero doesn't do anything.

[00:04:11]

>> Bianca Gandolfo: Nothing happens.

>> Speaker 3: Then you increment.

>> Bianca Gandolfo: Pivot location?

>> Speaker 3: And that would be one and then y would be one.

>> Speaker 2: So nothing will happen every time. Nothing will happen every time.

>> Bianca Gandolfo: So, pivot location is one. I is 1, so if array at i, which is 1, which is now 7, right?

[00:04:36] The next one was 7, is less than or equal to 4,

>> Bianca Gandolfo: Then what?

>> Speaker 2: Well, it's not gonna enter the condition.

>> Bianca Gandolfo: Yeah.

>> Speaker 2: Still nothing happens, but for a different reason.

>> Bianca Gandolfo: Yeah. So, what blanks do we need to fill here?

>> Speaker 3: They're not moving correctly.

[00:05:03]

>> Bianca Gandolfo: Yeah, what do we need to do?

>> Speaker 3: The four needs to be moving over a space every time, right?

>> Bianca Gandolfo: The four only needs to move when something is greater. When something is greater.

>> Speaker 2: Does this need an else statement?

>> Bianca Gandolfo: Yeah, let's plop an else in there.

[00:05:23] Come on.

>> Bianca Gandolfo: Else what? Well my spacing is weird.

>> Speaker 2: I think the issue is pivot location should have started at the other end. I don't see the point of keeping an i variable and a pivot location that are the same, that are in sync, because every.

>> Speaker 3: They're not going to be in sync.

[00:05:52]

>> Speaker 2: They won't always be in sync if you go into that else.

>> Speaker 3: It depends on what condition is executed. Why do you start the pivot location on the opposite side of the array?

>> Bianca Gandolfo: I don't know.

>> Speaker 2: So in this case you can take the one array length minus one, swap with seven.

[00:06:14]

>> Bianca Gandolfo: So far we're kind of saying, maybe this situation right here is doing something that maybe isn't important. Maybe, but we don't know.