Data Structures and Algorithms in JavaScript

# Quick Sort Review Part 2

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Quick Sort Review 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 wraps up her coverage of the Quick Sort algorithm by finishing her full code review the partition() and quicksort() methods. She documents each step as an array is sorted.

Get Unlimited Access Now

Transcript from the "Quick Sort Review Part 2" Lesson

[00:00:00]
>> Speaker 1: So now our array looks like this. It's updating. Then what's the next thing that happens, Tinbit?
>> Speaker 2: The pivot location will be the 1, too.
>> Speaker 1: Yep, pivot location is now 1, cuz we incremented. It was 0. And then, Miranda, what's the next thing that happens?
>> Speaker 2: And.

[00:00:30]
>> Speaker 1: I think I just got lost. [LAUGH]
>> Speaker 2: No worries, so we're inside of a loop.
>> Speaker 1: Yes.
>> Speaker 2: Yeah.
>> Speaker 1: So last time we left off, so Tinbit was kind of gesturing. That's our loop, this is our loop gesture.
>> Speaker 2: Yeah.
>> Speaker 1: [LAUGH]
>> Speaker 2: So it goes back through the 4 loop again.

[00:00:45]
>> Speaker 1: So now this is 3.
>> Speaker 2: Okay.
>> Speaker 1: And then what's the next thing that happens, Miranda?
>> Speaker 2: So the array i.
>> Speaker 1: So it's 4, right?
>> Speaker 1: 4 is the value, right?
>> Speaker 2: Mm-hm.
>> Speaker 1: Okay, less than-
>> Speaker 2: 0, 1, 2, 3, yep.
>> Speaker 1: Set it equal to.

[00:01:17]
>> Speaker 2: And then our pivot is 2.
>> Speaker 1: 2.
>> Speaker 2: Which is false.
>> Speaker 2: So we skip.
>> Speaker 2: Got it?
>> Speaker 1: Yes.
>> Speaker 2: That make sense?
>> Speaker 1: I think so.
>> Speaker 2: All right, then we loop again.
>> Speaker 2: All right?
>> Speaker 2: So is i less than hi at this point?

[00:01:44]
>> Speaker 2: This is our,
>> Speaker 2: Stop condition, 4 equals 4. So we break out of this 4 loop and we're done.
>> Speaker 2: Cool.
>> Speaker 2: And the last thing that we need to do is we're gonna move now our pivot, with our pivot location. This is a different implementation than the one we talked about yesterday, with the double swaps.

[00:02:13] Mm-hm, this is the Lomuto partition scheme.
>> Speaker 1: Okay, so that's why I was. [LAUGH]
>> Speaker 2: Yeah, it's a little bit different. So what this one does at the end, it waits till it's done and then it just swaps it at the end, which is way better. Cool, so we're gonna swap.

[00:02:35] Again we're just gonna put our swap on our stack. And what is our, this is our,
>> Speaker 2: Array, our pivot location is what did we change it? It's 1 now, right? Cuz we incremented it. And then hi is that's gonna be our pivot, which was what? 4, okay, so they're not equal.

[00:03:07] We're gonna keep going, temp array at i is 3. So this is gonna be 3, the value not the index. And now we're going to do some swapping, so here is our original 5, 4, 2. Here is our original and now we're gonna swap it. Array at i is gonna become, or i1 is gonna become 2.

[00:03:37] And now it's just going to stay like that. And then we're gonna edit this one. i2, which is our hi is gonna be our temp, which is 3.
>> Speaker 2: Cool? Awesome, so that is swapped. And we return to our array, here is our array.
>> Speaker 2: It returns out here, and we're gonna return the pivot location.

[00:04:06] This is another important thing. Our pivot location is 1. So we had pop this off, moving on, the pivot location is now 1. We're returning from this function, so we're popping off this function.
>> Speaker 2: Now, we're going back to where we first went inside of the function. p is now 1 because we returned our pivot location, which is 1.

[00:04:39]
>> Speaker 2: Got it, and our new array looks like this.
>> Speaker 2: 5, 3.
>> Speaker 2: Yeah, we're there, are we all there?
>> Speaker 2: Any questions about how we got here?
>> Speaker 2: No, can I have just one clarifying question?
>> Speaker 1: Which one is the pivot again? [LAUGH]
>> Speaker 2: The pivot is the one that you wanna move to its final place.

[00:05:18] So it was 2.
>> Speaker 1: It was 2, okay, that's-
>> Speaker 2: It was 2, yeah.
>> Speaker 1: But now we're gonna-
>> Speaker 2: Now we're gonna run it, now we're gonna jump into a recursion. So once your pivot finds its place, you then do the same thing. You partition the right and the left.

[00:05:40] And that's why we return the pivot location so that when we get here, we're gonna quicksort relative to the pivot location.
>> Speaker 2: Cool?
>> Speaker 1: The pivot may not always be in that position, right? So why do you, -1 is to get the index, right?
>> Speaker 2: So the pivot is at index 1.

[00:06:09]
>> Speaker 1: Right, so why would you subtract 1?
>> Speaker 2: The end of it as at 1 before. So this one is going to quicksort starting at 0 to p-1, which is just one single element, right? So that's just gonna return pretty quick, cuz it's just one element.
>> Speaker 2: Then this one-

[00:06:33]
>> Speaker 1: I guess, so if the pivot were in say, the [COUGH] index of 2, would you need to do p-2?
>> Speaker 2: No it's always gonna be p-1.
>> Speaker 1: Just the one right beside it, okay.
>> Speaker 2: Because you just want the one on the left. This could be super long,

[00:06:49]
>> Speaker 1: Okay
>> Speaker 2: And you just wanna get everything to the left.
>> Speaker 1: Got it.
>> Speaker 2: Yeah.
>> Speaker 2: And then for this one it's everything to the right. And that's because we now know, whoops. We now know that the 2 is in its final place, we don't need to sort it anymore.

[00:07:06] Now we have to do the sides, cool? All right, all right. So we're gonna pass in our array, lo, this is 0. p- 1 is also 0.
>> Speaker 2: So we can just skip this if that's okay. Is everyone fine with skipping this? It's gonna return pretty quick.
>> Speaker 2: Okay, so we're gonna skip that.

[00:07:39]
>> Speaker 2: And we're gonna do the right side, p+1 is 2 and then hi is 4. All right, so then we run our quicksort. And again, we're leaving off right here, just as a reference point. Okay, here we go
>> Speaker 2: All right? So lo at this point is not undefined.

[00:08:11] hi, also not undefined. So we will just keep this 2 and 4. So if lo, 2, is less than 4, we're gonna loop. I'm sorry, we're gonna partition.
>> Speaker 2: Okay, so again, we have the same values here. At this point, everything on the left is sorted.

[00:08:55] Now we're gonna start working on indexes 2 through 4. All right, so our pivot is gonna be 3.
>> Speaker 2: Our lo is 2. So while 2 < 4, we will loop here.
>> Speaker 2: So array at i, what's array at i?
>> Speaker 1: 5.
>> Speaker 2: 5 <= to our pivot, which is 3.

[00:09:32] Is that true? Nope, false. So we're gonna skip over. We're gonna loop again.
>> Speaker 2: Oops, now this is 3. Is 4 less than 3?
>> Speaker 2: Nope, so we'll skip again.
>> Speaker 2: Uh-oh.
>> Speaker 2: 4 less than 4? Nope, so we break out. So we swap.
>> Speaker 2: Are we following still, we're good?

[00:10:11]
>> Speaker 2: So our pivot location,
>> Speaker 2: Still the same.
>> Speaker 2: All right, so we're gonna swap our pivot location with our hi. So what that's gonna do is we're gonna swap a 5 with 3.
>> Speaker 2: Cool? And this, as you can see, since our list was mostly sorted, it's a pretty inefficient algorithm, right?

[00:10:43] Cuz now, our list is already sorted and we still have more recursion to do.
>> Speaker 2: All right, so our pivot location is 2. And then we start all over again sorting the left and the right, or I'm sorry.
>> Speaker 2: Just the right at this point.
>> Speaker 2: Cool?
>> Speaker 1: I mean, to me it looks like it's kind of chaotic, but it brings order faster.

[00:11:20] Is that what it is?
>> Speaker 2: Yeah, so on the average case, it's for this kind of sort, it's the fastest sort. And so most native implementations of this sort are going to be a quicksort underneath. But there are some times when its slower. And that's why it's important to recognize the limitations of a quicksort.

[00:11:39] Which is if it's mostly sorted, or if you chose the highest one every time, it becomes n squared. And you might as well just do a bubble sort at that point, yeah.