Quick Sort

[00:00:00]
>> The next thing that we wanna talk about is quick sort. So every time that you call .sort in JavaScript, usually it's calling merge sort, sometimes it calls quick sort. And when I talk about that, I'm actually just talking about this, right, where it's you call, on an array .sort, and it gives you an array back that is sorted, right, that's what I mean when I say like .sort.

[00:00:29]
Most of the time it calls merge sort, for the reasons that we talked about previously, which is it's stable, it's average case scenario is really good, all those kinda things. Quick sort has some interesting properties, but one, it's better spatially in terms of that it uses uses less memory to do, so occasionally engines like V8 at least it used to, I'm not sure if it does anymore.

[00:00:56]
Sometimes we'll call quick sort, it just depends. Okay, so it is another what we call divide and conquer algorithm. When I say divide and conquer, you can basically just replace that with recursive, right, cuz you're dividing the big problem into smaller problems, it's divide and conquer. It takes kind of a similar approach that it's gonna break a big array down into smaller arrays.

[00:01:27]
But it does throw in a slightly different fashion, so let's talk about that. So let's say we have this array, this array here of 4, 9, 3, 5, it's gonna choose what's called a pivot. Right, so a pivot is going to be the last number here, the 5.

[00:01:46]
Everything that's smaller than the pivot is gonna be put into a left array. Everything that's larger than the pivot is going to be put into the right array, right?. So this is the pivot 5, 5 has made the pivot since this last thing array and then we're going to divide this into two arrays.

[00:02:04]
Four and three because they're smaller than five are gonna be put into a left array. So 4, 3 get put into this array and 9 is the only one that's bigger than 5, so it gets put into a right array, okay? Then we call quick sort on this array here 4,3 and we call quick sort, again on 9, okay?

[00:02:25]
Let's go down to 4,3, 3 is made the pivot. Everything that is smaller gets put into a left array, which is nothing, and everything that's bigger gets put into a right array, which is just 4. Those both immediately return because those are both base cases, right? The base cases either length 0 or length 1, right, cuz those are already sorted.

[00:02:46]
And then what you do is you call concat on left array pivot, right array. So in this case the pivot was 3, the left array was empty array, and the right array was 4. So it's left array, which is blank, nothing, pivot which is 3, and then right array which is 4, okay?

[00:03:13]
So then this returns [3, 4] from this quick sort called here. And then we have 9 here, right, so this is gonna be this one here, base case returns 9. And then up here, we're gonna call concat on left array 3, 4 pivot, which is 5, and then right array, which is 9, so we end up with 3, 4, 5, 9.

[00:03:42]
Kinda clever, right, so unlike merge sort, we all are gonna have one function. The one function is just gonna be the quick sort function that's it and that's basically the whole thing. That's what quick sort is in a nutshell. I've kind of found this for you, which is a visual representation of it.

[00:04:07]
It is actually possible to do quick sort in place without actually breaking it down into separate arrays, which gives it much better spatial complexity. Don't worry about that today, today just use all the arrays let's go hog wild with all the arrays. This is easier to conceptualize, but just know that it is possible to do it in place.

[00:04:30]
So, one thing I wanted to call out here, which people kind of find confusing. Notice when I do the breakdown here from [4, 9], I make 5 pivot, and I have [4, 9, 3]. Notice that the pivot doesn't go into either array, right? So I have [4, 3] in one array and I have [9] in the other array and 5 is not in either one.

[00:04:53]
Some people find that confusing just keep in mind the pivot doesn't go into either array. Okay, let's talk about big O. So what's the worst case for a quick sort? Imagine if this was [1,2,3,4,5,6,7], 7 was the pivot, 7 is the largest item in the array. So that means everything is gonna go on the left array, and nothing's gonna go on the right array, and it's gonna keep breaking down that array that way.

[00:05:29]
So the worst case there is that you get no benefit from the recursion and you end up with n squared, right? Because every item is gonna be looked at and compared to every other item in the array. So sorted lists are actually a disaster for quick sort, same with reverse sorted, right?

[00:05:45]
Cuz you have the same problem everything goes in the right array. There are ways to mitigate that risk. Which you can actually instead of just saying automatically 5 is the pivot, you could say, I'm gonna look at 4, 9 and 5 and I'm gonna find the middle most elements and make that my pivot, this is called quick sort 3.

[00:06:04]
In which case you end up with a much better average case scenario of just n log n, right, which is the average case scenario. But the way that we're gonna do it today, we're not doing quick sort three, we're just gonna do quick sort. The worst case scenario is a sort of list.

[00:06:21]
What's the best case scenario? The more shuffled the array is the better quick sort is. So that's both the best case in mostly the average case as well, which is n log n, right? Because not every element is being compared to every other elements in the array. So we end up with n log n just like merge sort, but it has better spatial complexity and technically can probably go a little faster.

[00:06:45]
So some better coefficients. And we are gonna do it as a nondestructive version, but it is possible to do a destructive version which has better spatial complexity. So I think the way that we're gonna do it, it would be basically n in terms of spatial complexity. But if you do it destructively, you still have to make some allocations on the stack.

[00:07:11]
Which would make it log n, cool. There are some variations of quick sort, like quicksort 3, that's what I was telling you about just before. There are some other variations but they're almost all variations around how you choose the pivot, cuz that's obviously pivotal, nice. [LAUGH] It's pivotal, I'm just seeing everyone shaking their heads like dear God, it's too late for a dad joke like that, [LAUGH].

[00:07:41]
It's very important how you choose your pivot. So that's where all the variations of quick sort come in and you can actually check that out on the Wikipedia page that it'll run down a bunch of those variations