Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Debugging the Quick Sort Algorithm" 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:

As a bonus exercise, Bianca re-codes the Quick Sort partition() method with the group. As before, the partition method() is passed the array as well as first and last values. The first value is the pivot location. The last value is the pivot point. The method then proceeds to loop through the array to compare the elements to the pivot and make any necessary swaps.

Get Unlimited Access Now

Transcript from the "Debugging the Quick Sort Algorithm" Lesson

[00:00:00]
>> Bianca Gandolfo: Now that we have reviewed the concept, let's check our pseudocode and make sure it matches. So what's the first thing that we need to do? If you want me to erase this whole thing and we can start from scratch? Or you wanna edit it? It's always harder to debug?

[00:00:14]
>> Speaker 2: Erase it.
>> Bianca Gandolfo: You wanna erase it and start over? Just know in real life you can't always erase it and start over. But, since I like you, we can do it that way. Okay.
>> Speaker 3: Well, first of all, I think you only need an array as an argument because you're gonna set the pivot point and pivot location.

[00:00:34]
>> Bianca Gandolfo: Well, so because it's gonna be recursive, it's gonna change.
>> Bianca Gandolfo: Yeah.
>> Speaker 3: Right, okay.
>> Bianca Gandolfo: And you're always gonna pass the entire array every time. That's why we do it that way.
>> Speaker 3: Okay.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: I forgot what order I had things in.
>> Bianca Gandolfo: That's about right.

[00:00:54] It's good enough. I'm missing one. Should we put the 6 here? Is that a good spot for it? Okay, so here's our original. We're gonna erase that one. Okay, so tell me what is the first thing we need to do?
>> Bianca Gandolfo: We have to initialize a couple things, right?

[00:01:19] What are those things?
>> Speaker 3: Pivot location and the pivot?
>> Bianca Gandolfo: All right,
>> Bianca Gandolfo: So our pivot location, we're gonna start it at lo, which is gonna be zero at the beginning.
>> Bianca Gandolfo: Pivot, you guys didn't even say it. Well.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: I'll pretend like you did. Someone whispered it, I heard it in their mind.

[00:01:43] Okay, so we did some initializations here. We have our pivot is gonna be 4 and our pivot location just initializes at the beginning. We're good? So what's the first thing we need to do?
>> Bianca Gandolfo: I know some people did the pseudocode cuz I saw it.
>> Speaker 3: Did you do a loop?

[00:02:07]
>> Bianca Gandolfo: Yeah, loop through what?
>> Speaker 3: The length of the array.
>> Bianca Gandolfo: Loop.
>> Speaker 3: From lo to hi.
>> Bianca Gandolfo: From lo to hi, why?
>> Speaker 3: Cuz that's the chunk of the array that we're gonna be sorting, so.
>> Bianca Gandolfo: Okay.
>> Speaker 3: In the beginning it's 0 to the end, so we're gonna sort the whole thing.

[00:02:34] But as we go down recursively it'll be like, from 0 to 5 or whatever.
>> Bianca Gandolfo: Okay, we'll go from there. So let's say we loop from the beginning to the top. What are we gonna do in every loop?
>> Speaker 3: We're gonna compare hi to the-
>> Bianca Gandolfo: Compare the pivot.

[00:02:59]
>> Speaker 3: Right, to,
>> Speaker 3: The like, yeah, r sub i, whatever the index is.
>> Bianca Gandolfo: Right, cuz you wanna, we're gonna keep track of the pivot location, right? Which is the beginning. Starts at the beginning.
>> Speaker 4: Should pivot be hi, or should it be array? High index of array?

[00:03:28]
>> Bianca Gandolfo: Hi is the last.
>> Bianca Gandolfo: We can like-
>> Speaker 4: But are those numbers integers or are they-
>> Bianca Gandolfo: Yeah, they're indices.
>> Speaker 4: They're both indices?
>> Bianca Gandolfo: Mm-hm. Well, this one shouldn't be. Yeah, that one shouldn't be. Good catch. So we wanted that one to be the value, or actually-

[00:03:54]
>> Speaker 4: You could use indices and just compare in-
>> Bianca Gandolfo: Yeah.
>> Speaker 4: The indexed array or that way, it's like it doesn't matter.
>> Bianca Gandolfo: Yeah, it doesn't really matter. You just have to be able to compare.
>> Speaker 4: If you do it as an index, then the comparison would be array at pivot to array at pivotLoc.

[00:04:14]
>> Bianca Gandolfo: Yeah.
>> Speaker 3: So it's-
>> Bianca Gandolfo: Also we have to, we'd have to update it every time.
>> Speaker 3: Yep.
>> Bianca Gandolfo: So if we just save the value we can just compare it directly. But it can get tricky if we had doubles, right, something to keep in mind. Well, let's pretend we don't, let's make our life easy.

[00:04:34] Cool, so we are comparing our pivot value to the value at our pivot location.
>> Bianca Gandolfo: Cool, so we compare 4 to 3. Now what happens? 3 is less than 4. What does that mean for us?
>> Speaker 4: So it definitely means we need to increment the pivot location.
>> Bianca Gandolfo: Yeah, and that's because our pivot location, everything to the left needs to be less.

[00:05:09] So we know if we increment it to 1, we now have, we meet part of that criteria, right? So we're moving closer to where we wanted to be. So if our, what were we saying, our pivot is greater than our current item here,
>> Bianca Gandolfo: What are we gonna do?

[00:05:41]
>> Bianca Gandolfo: Someone who didn't, how about Jen? What are we gonna do?
>> Bianca Gandolfo: So we just discovered that our pivot is greater than our 3.
>> Speaker 2: So then we increment the pivot location.
>> Bianca Gandolfo: Yep, awesome.
>> Bianca Gandolfo: What about our else?
>> Bianca Gandolfo: What happens in the else? So great, we did that.

[00:06:23] We looked, and then we move. Our pivot location is now 1. So I'll just keep this here. So this is a value, and this is the index.
>> Bianca Gandolfo: We're looping maybe. Okay, so we compared it. We incremented our pivot location, now it's 1.
>> Bianca Gandolfo: Now we're gonna loop again.

[00:06:51]
>> Bianca Gandolfo: So, let's say,
>> Bianca Gandolfo: All right, so now we're at index 1, true? So at index 1 we compare 7 to 4 and it's not less. So what do we do when 7 is greater then 4?
>> Speaker 2: We swap around.
>> Bianca Gandolfo: Swap them, yeah.
>> Bianca Gandolfo: So we, whoa, swap.

[00:07:22] You guys read caps as yelling?
>> Speaker 2: Yes.
>> Bianca Gandolfo: Swap the pivot.
>> Speaker 2: I would be so annoyed if you typed all of that uppercase. [LAUGH]
>> Bianca Gandolfo: With pivot. Do you guys know what I mean when I say the item, swap pivot location item? Or maybe I'll make it a little more clear.

[00:07:45] We'll say array at the pivot location with pivot, okay? So that means that we swap 7 with 4. Great, that's not exactly what we want, right? Then what do we need to do?
>> Bianca Gandolfo: How about our two gentlemen, Maurice and John? I know you guys know.
>> Speaker 3: Swap 5 and 4.

[00:08:11]
>> Bianca Gandolfo: Mm-hm, so swap the pivot with,
>> Bianca Gandolfo: The end of the array, right? Something like that. Maybe this one needs to- Okay, we say-
>> Speaker 2: In every case it's not going to be that.
>> Bianca Gandolfo: Yeah, so maybe that needs to change a little bit.
>> Bianca Gandolfo: So we'll make a note.

[00:08:42] Maybe we need to track this somewhere.
>> Speaker 4: But don't you think, if it's minus 1, the only way it's going to get to this point is if the number before it is higher, so we'll have to switch with that one.
>> Speaker 4: But never mind. [INAUDIBLE] I don't know if I need these or not.

[00:09:07] So carry, subtract one, and then kind of subtract another one after you do the swap, so kind of keep a count on that.
>> Bianca Gandolfo: Yeah, so that could be useful for us to keep track of the pivot location and not the pivot value. So we can increment it, or we can,

[00:09:28]
>> Bianca Gandolfo: We can say this is pivot and this is the pivot value or something.
>> Bianca Gandolfo: And then we can update this every time. That's one way to do it. Are you guys following here? So you just need to keep track of that somehow. I don't care how you do it.

[00:09:48] Cool, what else do we need to do?
>> Bianca Gandolfo: Shall we run our code and see if it works? Run it in our brains? Okay, so let's just keep going from where we were. So we're at 4, we're gonna loop again, we're gonna compare the pivot to our pivot location.

[00:10:11] Again, our pivot location is in the same place. We haven't incremented it yet so we're still at 1. So pivot location, is it less? No, it's not. So we're gonna do this case. We're gonna swap 4 with 5, and then we're gonna swap 1 with 4.
>> Bianca Gandolfo: Cool, we're gonna loop again, and our value, what loop are we at now, 3 or something?

[00:10:46]
>> Speaker 2: Yeah.
>> Bianca Gandolfo: We've looped three times, I think. Cool, so our pivot location is still 1. Is 1 less than 4?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Absolutely, so we increment our pivot location.
>> Speaker 2: My God, I understand that now.
>> Bianca Gandolfo: [LAUGH] Whoo hoo.
>> Speaker 2: I did it.
>> Bianca Gandolfo: Light bulbs.

[00:11:07] Okay, so we incremented our pivot location, and we're going to loop again. Is our pivot location less than 4? Yes, so then we increment it again. Is 6 less than 4? No, so we're gonna do our swaps.
>> Bianca Gandolfo: And then the one thing that we're not doing is catching when our pivot location is in its final place in the world.

[00:11:39] So where should we do that?
>> Speaker 4: Could we wrap the whole loop in a while loop? Would that be weird?
>> Speaker 2: You probably wouldn't want to do that. I mean, we can just figure out, okay, we just want to break from this loop. We don't want to loop more cuz that would make it some crazy, I don't know.

[00:12:02]
>> Speaker 3: So then an else if kind of thing.
>> Speaker 2: Mm-hm.
>> Bianca Gandolfo: So, we're almost at 4, so here's our to do. Add in your break for when the pivot has landed. It's almost like a pilot, or a plane. So when your pivot has landed. Cool, can you guys do that?

[00:12:26] And that would be your partition.