Data Structures and Algorithms in JavaScript

# Reviewing the Pseudocode

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

## With the Quick Sort pseudocode complete, Bianca takes a few minutes to review the entire algorithm. She asks the audience to guide her through the pseudocode and apply the algorithm to a small array.

Get Unlimited Access Now

Transcript from the "Reviewing the Pseudocode" Lesson

[00:00:00]
>> Bianca Gandolfo: Alright so lets debug this pseudocode. So we have our partition, we know our partition is going to be a recursive element of our algorithm, right? And that's why we have low and high in the entire array because every time we partition. We're going to pass it and give it a different range of elements to partition.

[00:00:25] The first time we do this we're going to partition the entire array and that's what we're going to be thinking about right now. Okay? Are we good?
>> class: Yeah.
>> Bianca Gandolfo: So this is what we have, we choose the last element as a pivot, which at this point is the end of the array.

[00:00:47] Here, I'm going to move this over, so we have lots of space. And then I'm going to move over.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: Cool, so here's our thing.
>> Bianca Gandolfo: All right, we reset it back to how it was. So just a recap of what we wanna do here.

[00:01:29] Is, we want to think. Okay. Our pivot point, which is going to be the last one. We want to move it to its final location in the array. We know it's there when all of the elements to the left are less, even if it's unsorted. And all the elements to the right are greater, even if that is unsorted.

[00:01:50] We know that the 4 is gonna be in its final place inside of the array.
>> Bianca Gandolfo: Yeah. So that's the goal here. And so what we wanna do, as we're doing this we wanna keep track of everywhere that is, the part of the array that's less.
>> Bianca Gandolfo: Than our pivot point, we wanna keep track of that.

[00:02:17] And what else do we wanna keep track of? I wanna keep track of our actual element in question and what else? Is that it? That's basically it, am I missing anything? No? Okay, so the first thing we wanna do. Is, so we start at the beginning, the beginning is our pivot location, so 3, so our pivot location starts at 0, so 3, is 3 less than four?

[00:02:50] Yeah, so that's great, so we increment our pivot location by 1 so, now our pivot location is here, index 1. And we compare, is 7 less than 4? Notice not, okay? Because it's not we wanna make sure that our 7 get moved to the end. And our 4, need to increment to the left.

[00:03:19] So in it's current location minus 1, okay? So an easy way to do that is we can swap 4 with 7 and then we have a second swap, we'll swap 4 with 5. Note that our pivot location is still 1, okay? This is important, because we need to make sure that whenever our pivot location is, everything to the left, including itself, needs to be less then 4.

[00:03:55] Okay. So we're good with the pivot location? So the next thing we do. Is we compare the same index, we're still at 1, 5 to 4. Is 5 less than 4, no it's not, so we're gonna swap again.
>> Bianca Gandolfo: Oops, and then 2, 4, awesome. Again we're still here, now we go to, we loop again, back to where we were.

[00:04:36] We check 2, is 2 less than 4? Yes, so we increment now our pivot location up. So there's our pivot location now. Then we check is 6 less than 4. No it's not. So we're going to do our swaps. All right. So now we're still at the same pivot location index 2 and what we're gonna check is 1 less than 4.

[00:05:18] Yes and then we increment our pivot location. Once our pivot location meets our pivot that's when we know our pivot is in it's final place. I don't want to say final resting place cuz that sounds kind of morbid.
>> class: [LAUGH]
>> Bianca Gandolfo: But it's in it's final Place in the world, it's found it's place, it's purpose which is the the V smack dab in the middle.

[00:05:41] Ya?