Quick Sort Practice

[00:00:00]
>> I want to give you a shot to go do this, so we're gonna pop back over to quick sort here, quick sort, okay, and so, here we're gonna say base case, right? So what is base case, array of length zero or one in this particular case, we actually will see lots of arrays of length zero, right?

[00:00:30]
Because if there's nothing in the left array, we're going to call quick sort on that, and we need to handle that, so make sure you're providing for length zero or length one. Choose pivot. Here we're gonna separate into left and right arrays. Call quick sort. On, left and right arrays.

[00:01:01]
Return, Left. Can cat, Pivot, great. That's it, that's the whole thing. Probably, I might have diagrammed that a little too out for you, but everyone can use a wind today [LAUGH] so I'm gonna give you 15 minutes to go ahead and get this done. And then you and I are gonna come back and do this together, and again make sure you move test out skip there, and yeah again this sorting visualizer is not gonna help you with this.

[00:01:41]
So the question is this, if I have duplicate in my array, so if I have five and my pivot is five does the duplicate five go on the left or does it go on the right? And the answer is, doesn't matter, because it's gonna get sorted either way and I don't believe quicksort is stable, off top my head have to look.

[00:02:03]
But in any case, in general with those kind of calls, it's just be consistent, so, if it's gonna go left always put in the left, if it's gonna go right always put it in the right, but in the end it just be consistent. Let's go ahead and go through this, so base case here, if nums style length is less than or equal to one, then you just return nums.

[00:02:40]
Okay, gonna choose a pivot, and in our case, we're just always going to go with the last one, so const pivot equals nums of nums dot length minus one. So that's gonna be our pivot. And we'll separate into left and right arrays, so we're gonna say const left equals empty array, const right equals empty array.

[00:03:20]
And then we're gonna say, four let I equals zero, I is less than nums dot length minus one, cuz the pivot is the last number, so we don't wanna capture that one, I plus, plus. And we're gonna say if nums of I is less than pivot. Then we're going to say left dot push nums of I else, all right, dot push nums of I, okay, so now we have a pivot we have a left array which contains everything is smaller.

[00:04:23]
We have a right array which contains everything that's larger, so we can say const sorted left, equals quick sort left, const sorted right equals quick Sort right. And then I actually think that's just straight up valid JavaScript, so I think you can just say that, this would actually have to be sorted left, sorted left, sorted, right.

[00:05:13]
That works, after I wrote the skip, and quick sort, do right, there it is, so pivots fine, even though this is just a number concat is smart enough to say it's like this is just a number. It's not an array, so I'm just going to insert this as an item in the array.

[00:05:37]
If you look to my course notes, I actually combined two these three lines into one and I said return dot dot dot quick sort left, pivot dot dot dot quicksort right, like this. This should work as well, but let's just make sure quick, so where are you right there, click play, and you can see there that also works as well.

[00:06:11]
This is called the spread operator, it's new as of yes five, so I think it's actually like six years old now, this is saying like, this is an array please spread this out over this new array, right? But this line and this line end up being equivalent.