Data Structures and Algorithms in JavaScript

# Pseudocoding Quick Sort Part 2

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Pseudocoding Quick Sort Part 2" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

## Bianca completes her pseudocode demonstration of the Merge Sort algorithm. In this part, she looks at swapping an element that is greater than the pivot.

Get Unlimited Access Now

Transcript from the "Pseudocoding Quick Sort Part 2" Lesson

[00:00:00]
>> Bianca Gandolfo: So I think our next question is, so if the current element in the array is greater than our pivot point, what do we do?
>> Speaker 2: We need to go on the other side of the pivot point.
>> Bianca Gandolfo: Yep, so that's our else, right? So how do we do that is my next question?

[00:00:21]
>> Speaker 2: We need to know the,
>> Speaker 3: Do you need to do two swaps? So the first one is the other element, minus 1 that's 7, and then 4 in that?
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: Say that slower. What did you say? So the last one, okay?
>> Speaker 3: Minus 1.
>> Bianca Gandolfo: Okay.

[00:00:49]
>> Speaker 3: With 7, yes.
>> Bianca Gandolfo: With 7, which is what?
>> Speaker 3: i = 1.
>> Bianca Gandolfo: So, with.
>> Speaker 3: With i.
>> Bianca Gandolfo: arr(i)?
>> Speaker 3: Yeah.
>> Bianca Gandolfo: Okay, cool. So, we swap that. So now, 4 is swapped with 7.
>> Bianca Gandolfo: Okay so we're partly there, because we remember that we don't want 4.

[00:01:33]
>> Speaker 2: What about the other thing that you shoved at the end or the beginning of the array?
>> Bianca Gandolfo: You mean the 5?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Yeah, so what do we do with the 5?
>> Speaker 2: It needs to go where the 7 was, I mean not 7.
>> Speaker 3: Where the 4 is now.

[00:01:48]
>> Bianca Gandolfo: Where the 4 is now. Wait, did the 4 go to the front? So we did swap the 4 to the front. Why did the 4 go to the front?
>> Speaker 2: Cuz that's, I'm a robot.
>> Bianca Gandolfo: Did the 4 go to the front, and then it goes to the, it goes around in a circle?

[00:02:04]
>> Speaker 2: You could do it that way. There are definitely two swaps happening.
>> Bianca Gandolfo: Okay, okay, okay, okay, I understand.
>> Speaker 2: Cool, so what's the next swap we have to do.
>> Bianca Gandolfo: So if the 4 is down here and what's at the end?
>> Speaker 2: 7.
>> Bianca Gandolfo: The 7's at the end?

[00:02:21]
>> Speaker 2: Here I'll put a note of what we have. So, so far we had [3, 7, ..] whatever.
>> Speaker 2: 4, 5, right, we had some things in between. So what we did, the first thing we did was we looked at it and something, maybe nothing happened. Maybe that was a weird thing, I don't know.

[00:02:54] So we're like, okay, it didn't move, it didn't do anything wrong, but why is it there? That was our, what we came up with for that. Then we went to the next one, and that's when we made our l statement. And we swapped our 7 with our 4.

[00:03:13]
>> Bianca Gandolfo: The 4 needs to swap with the 5.
>> Speaker 2: Yep.
>> Bianca Gandolfo: The picture shows that we just took 7 to the last of 4 as it is. And according to the data, we didn't take 4 to the second line.
>> Speaker 2: Yeah, so now we need to move it to 5, right?

[00:03:34]
>> Bianca Gandolfo: Just to result moving, if you put 7 in the last place, just 4 would be in the position of 5.
>> Speaker 2: Yes.
>> Bianca Gandolfo: You don't need to take 4 to-
>> Speaker 2: So you're saying hey, maybe we don't even have to swap twice. Maybe we save 4, put 4, then put 5, is that what you mean, save 4 in a variable?

[00:04:01]
>> Bianca Gandolfo: For instance 4 is on the position not 10, right?
>> Speaker 2: Yeah, we don't want it there.
>> Bianca Gandolfo: Yeah, just if you move 7 to the, yeah.
>> Speaker 2: 7 like this?
>> Bianca Gandolfo: Move 7 to the last.
>> Bianca Gandolfo: And you can, no, leave 4 as in the previous position.l

[00:04:28]
>> Speaker 2: So the thing is is that we have to, if we're going to move 4 to the end, we're going to overwrite it. If we're moving 7 to the end, we're going to overwrite the 4.
>> Bianca Gandolfo: Just 4 take the position of, if you move 7 to the position 4, 4 takes the position of 5 so everything is lined up.

[00:04:49] The diagram cross like that.
>> Speaker 2: Yeah, so,
>> Speaker 2: So what you're saying then is you want to save 4 in a variable,
>> Speaker 2: Switch these two.
>> Bianca Gandolfo: We haven't done anything [INAUDIBLE].
>> Speaker 2: Then you wanna move five to-
>> Speaker 2: i, right?
>> Bianca Gandolfo: Yeah.
>> Speaker 2: And then you're gonna move 4 to whatever.

[00:05:36]
>> Bianca Gandolfo: 5.
>> Speaker 2: Yeah, so what was that array.length- 2?
>> Bianca Gandolfo: Would you be able to keep track of that?
>> Speaker 2: Yes, so how are you gonna keep track of that?
>> Bianca Gandolfo: We do.
>> Bianca Gandolfo: Easily.
>> Speaker 2: If you did like length- i.
>> Speaker 2: Would be a swap.
>> Bianca Gandolfo: Yep, well i at this- 1,- i would be, cuz i is 1, right, at this point.

[00:06:16]
>> Speaker 2: Well yeah, because as it goes up it will be going backwards.
>> Bianca Gandolfo: Yeah, we want it to go backwards for sure.
>> [INAUDIBLE]
>> Speaker 2: Do we always want the first swap to be length- 1? Shouldn't that one be length- i?
>> Bianca Gandolfo: Yeah, let's do it.
>> Speaker 2: Would it be simpler to keep that as it was, and just do it twice?

[00:06:47]
>> Bianca Gandolfo: Do what twice?
>> Speaker 2: The swap, the one that's length- 1. The line that you're on there?
>> Bianca Gandolfo: Just do this twice?
>> Speaker 2: Yeah, but with- 1 not- i.
>> [INAUDIBLE]
>> Bianca Gandolfo: Yeah, so there are a few ways of doing this.
>> [INAUDIBLE]
>> Speaker 2: So you can swap this, with this, well, if we go back to how we were.

[00:07:16]
>> [INAUDIBLE]
>> Bianca Gandolfo: So you can swap this one with this one, right, 4 and then 7 and then you can swap 4 and 5.
>> Speaker 2: That's what I meant.
>> Bianca Gandolfo: That's what two swaps, yeah, yeah, yeah. So you could totally do that.
>> [INAUDIBLE]
>> Speaker 2: Cool.
>> [INAUDIBLE]

[00:07:46]
>> Bianca Gandolfo: So is this gonna work? Have we saved the day? Broken pseudocode, this is pseudo pseudocode. Not even real pseudocode pseudocode, does this work? Is this gonna do what we need it to do?
>> Bianca Gandolfo: I know, let's walk through it. So maybe we aren't clear if this even works.

[00:08:17]
>> Bianca Gandolfo: Right, that's where we left with that. Do we have opinions on it yet?
>> Bianca Gandolfo: No one has opinions?
>> Bianca Gandolfo: That's okay.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So we have no opinions on that.
>> Speaker 2: What was the question?
>> Bianca Gandolfo: So the question is, does this work? If we turn this pseudocode into real code, is this our solution?

[00:08:48] If I just said okay, see you guys later, go code this now. Would you guys feel confident to turn this into a real code that partitions correctly?
>> Speaker 2: Just the partition part, not the, because we.
>> Bianca Gandolfo: Yeah, this is just the partition part.
>> Speaker 2: Yeah, this is just the partition part.

[00:09:09] Yeah, for this the partition,
>> Speaker 2: Isn't gonna do the slicing part. It is the slicing part, but it doesn't do it actively. If you see the Quick Sort code, it sorts it. It makes a sub array in here, but we'll get to that.