Data Structures and Algorithms in JavaScript

# Quick Sort Review Part 1

This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Quick Sort Review Part 1" 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 combines the quicksort() method with the partition() method to perform a full code review of the entire Quick Sort algorithm. She continues tracing through the code and documenting each swap as she fields questions from the audience.

Get Unlimited Access Now

Transcript from the "Quick Sort Review Part 1" Lesson

[00:00:00]
>> Bianca Gandolfo: Before we get into trees, we are going to review quick sort. So we are going to do the thing that we do, where I pretend to run the code and we make a call stack and kind of trace everything, except this time we're going to do it with your help, right?

[00:00:19] So we're going to start at Andy, go to Maurice, John, Timbit all the way down and then we're going to go in this loop and we're going to talk about how the values are changing, the order in which this code is executing. Don't forget to tell me when to put something on the stack and when to pop it off the call stack, okay?

[00:00:36] Are you ready? Any questions before we jump in? About how this will work?
>> Speaker 2: Were you just gonna kind of talk through.
>> Bianca Gandolfo: Mm-hm, yep. Okay let me make this the right size.
>> Bianca Gandolfo: Okay, all right.
>> Bianca Gandolfo: This one's so long it's hard to fit on one.
>> Bianca Gandolfo: Okay, all right.

[00:01:16]
>> Bianca Gandolfo: So we just pasted this body of code somewhere and we hit run. And we hit enter in our console, perhaps. What's the first thing that's going to happen?
>> Speaker 3: So the quicksort function will run. We're passing in an array, but we're not passing lo and hi. So the first If statement will be true, and it'll set lo equal to zero.

[00:01:42]
>> Bianca Gandolfo: Awesome, perfect. So we have quick sort, we pass in the values, which means we're going to cue up this, right. Our stack's going to be on the right this, since we don't have that much space. Our array looks like this. And lo and hi is undefined. So just like Andy said, oops, just like Andy said we are going to initialize them at zero in the last index of the array.

[00:02:12] That's what this is, awesome, okay, there it is.
>> Speaker 2: So then it compares the lo with the hi?
>> Bianca Gandolfo: Hm. So lo is zero, what is hi?
>> Speaker 2: High is five.
>> Bianca Gandolfo: Yeah, four right.
>> Speaker 2: Cool.
>> Bianca Gandolfo: Zero, one, two, three, four.
>> Speaker 2: Both yes.
>> Bianca Gandolfo: Yep. So is zero less than four?

[00:02:41] True. And then we're gonna jump into the body of the function. John, you wanna go next?
>> John: Is high four or is it two? Because the length is five but you subtract one to get index of four.
>> Bianca Gandolfo: Yep.
>> John: Zero, one, two, three, the index is for right?

[00:03:02]
>> Bianca Gandolfo: Yeah.
>> John: So that would be two. Or am I confused?
>> Bianca Gandolfo: Yeah, but we're just saving the index number here. We're not actually accessing the value.
>> John: Right. Okay. Got it.
>> Bianca Gandolfo: Good question though.
>> John: All right, so since it's true,
>> John: Then you're going to run this partition function with the array and zero and four.

[00:03:36]
>> Bianca Gandolfo: Zero and four. Great, I'm going to put it under there so we can see it. So I'm gonna copy and paste our partition function over. All right, so just a reminder of what our values are, we're gonna put it here. Who's next? Timbit, do you want to go next?

[00:04:00]
>> Timbit: Either increase the indexes too or
>> Bianca Gandolfo: For this one?
>> Timbit: Yeah, that one is for the pivot in the example.
>> Bianca Gandolfo: Yeah, this is two. So high is four. We're accessing two. That's our pivot, and then what's our pivot location?
>> Timbit: One.
>> Bianca Gandolfo: Zero, right? Because we passed in zero.

[00:04:36] Which, again, this is an index, and this is the value, and remember here the pivot, that is the element that we want to have in its final place after all the swapping happens. Okay? The pivot location is where we're going to keep track of where that final location should be.

[00:04:57] Cool? All right. Miranda, what's the next thing that happens? So in the for loop it sets I to pivot location zero. Zero is, is zero less than two, right? So this is just gonna loop from zero to four. Right, cuz lo is zero. We have it over here.

[00:05:34] And hi is four. So that's what this does right here.
>> Bianca Gandolfo: And then we'll enter into the body of the loop. And we'll come across this condition. What does this condition say, David?
>> Timbit: Well, we're comparing the value and position i with the pivot. And i is zero, the value and position zero is five.

[00:06:01] And so we're asking is 5 less than or equal to 2, and I believe that's false.
>> Bianca Gandolfo: Yeah, last time I checked. Unless you guys are reading 1984.
>> Timbit: Based on my training, I'd say that's a false statement.
>> Bianca Gandolfo: [LAUGH] Okay. False. So since it's false, we're going to skip this If statement.

[00:06:21] And then what happens next?
>> Timbit: And i is incremented when we re-enter the loop with i equals one.
>> Bianca Gandolfo: Yep, so we'll increment, now i is one, still four. What's the next thing we do Jenn? Well, the increment in the array, so the one is three, three is not less than or equal to two, so false, false again.

[00:06:53] All right.
>> Bianca Gandolfo: Then what happens, Rosie?
>> Rosie: Pass, I haven't had a chance to look at this. [LAUGH]
>> Bianca Gandolfo: Okay. Well we're just, since this is false we're just gonna skip over the body of the if statement. And then we're gonna enter into the loop again. Should we pass it over to you Andy?

[00:07:11]
>> Andy: Yeah, so that'll get incremented again. And we'll go in for another round. This time it's-
>> Bianca Gandolfo: Oops, sorry
>> Bianca Gandolfo: I'm sorry. [LAUGH] Wait. Two. Two.
>> Andy: [LAUGH]
>> Bianca Gandolfo: There's two and then.
>> Andy: Makes that one.
>> Bianca Gandolfo: Yep.
>> Andy: Which is less than two.
>> Bianca Gandolfo: Whoo, we made it.

[00:07:36] So one is less than two. So then we're gonna enter into the body of this function.
>> Bianca Gandolfo: Maurice do you want to take a stab?
>> Maurice: So pivot location is,
>> Maurice: That's the value, right? No, that's the lo.
>> Bianca Gandolfo: Pivot location, yeah. We initialize it at zero.
>> Maurice: So that's two.

[00:08:04] So just swap-
>> Bianca Gandolfo: So we pass the entire array.
>> Maurice: Array.
>> Bianca Gandolfo: And we have the pivot location, which is zero. And we swap it with i, which is two.
>> Maurice: Is two.
>> Bianca Gandolfo: Cool. Should we take a look at what's going on in our swap now? Which I didn't copy over.

[00:08:28] Let me grab our swap for us. [SOUND] Swap.
>> Bianca Gandolfo: We'll put a swap down here.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: So we're gonna swap.
>> Bianca Gandolfo: So, this is where we leave off, right? Cuz we're jumping in to the swap. This is where we left off before.
>> Bianca Gandolfo: All right.

[00:09:09] So now we have our swap. We have our array.
>> Bianca Gandolfo: Zero and two. Okay, John, your turn.
>> John: Okay, so it evaluates if 0 and 2 are the same, which they are not.
>> Bianca Gandolfo: Okay.
>> John: So,
>> John: So then it keeps going, yeah. So then it puts 0 in the variable temp, it's just swapping them, of course, yeah.

[00:09:39]
>> Bianca Gandolfo: So what is temp at this point?
>> John: So temp is 0, I'm sorry.
>> Bianca Gandolfo: Temp is 5 right?
>> John: Because of the index right, yes so it's up there.
>> Bianca Gandolfo: Yeah.
>> John: So yeah temp is 5.
>> Bianca Gandolfo: So it's [INAUDIBLE] at 0 which is 5.
>> John: Yeah then 5 equals 1 or 5 becomes 1.

[00:10:04]
>> Bianca Gandolfo: So then we swap it so now our array looks something like what?
>> John: Like 1, 3.
>> Bianca Gandolfo: Backwards 5.
>> John: 4, 2.
>> Bianca Gandolfo: 4, 2. Okay.
>> John: And then
>> John: Sorry, so what is i2, i2 is 2 so 0, 1, 2 is 1, so 1 is now 5, or no.

[00:10:31]
>> Bianca Gandolfo: So actually, right that's what that looks like, there we go.
>> John: Yes okay, there we go, now it's 1, 3, 5, 4, 2.
>> Bianca Gandolfo: And now we're putting the five.
>> John: 1, 3, 5, 4, 2.
>> Bianca Gandolfo: Thank you. Got it. So we swap them. Great and we have this cancel out where we can move on with our lives and we're gonna return this array.

[00:10:58]
>> John: Is there any reason to return it?
>> Bianca Gandolfo: Hm?
>> John: Any reason to return the array?
>> Bianca Gandolfo: No, I don't think so.
>> Bianca Gandolfo: So, the reason it doesn't really matter that we are returning the arrays is because we are editing the same copy of this array for the entire function.

[00:11:18] So, we're not copying arrays and copying arrays and changing anything around. We're actually editing the same array. Even when we're doing the recursive calls, it's the same array. But this is probably just a generic swap function.
>> Bianca Gandolfo: Cool, so here we are. So we have a return. We're gonna pop it off, and we're gonna continue back where we were.