This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Quick Sort" Lesson
[00:00:00]
>> [MUSIC]
[00:00:04]
>> Brian Holt: We talked about merge sort just barely. And we're gonna talk about one more divide-and-conquer type algorithm, called Quick Sort. Before we get started, is there anyone have questions that they would like answered about any of the previous sorts about recursion, about big-O, any of that stuff?
>> Brian Holt: Okay, I must be explaining it perfectly that so awesome.
[00:00:31]
>> Brian Holt: So let's go down here to Quick Sort. Now like if you look at like the gift on this, it just looks erratic, right? Like what the hell is actually happening there. So it's actually not super helpful to visualize it but it's kind of fun to look at right?
[00:00:47] So Quick Sort is certainly one of the most powerful sorting algorithms out there and luckily it's actually not super hard to conceptualize, once you have a conceptualized merge sort because there's some similar ideas at play here. And when I mentioned above that JavaScript doesn't always do merge sort, at the times it is not doing merge so it's doing Quicksort, just so you know.
[00:01:16] Or some variation of Quicksort, the thing about Quicksort is there's like 70 variations of how to do Quicksort or we're gonna do like Quicksort like the original Quicksort. And all the variations aimed to solve one problem which is the pivot problem, but we'll talk about that at the end.
[00:01:35]
>> Brian Holt: So it's another divide and conquer, AKA it is recursive. But it takes a slightly different approach and the basic gist of Quicksort is you have your array, right? So let's draw out an array here.
>> Brian Holt: Okay, so you have an array of like,
>> Brian Holt: 5, 7, 4 9 and let's do 6, okay?
[00:02:09] So that's our array right there. Now the first we're gonna do is we're gonna pick up pivot, right? Now where you choose that pivot is up to you. I recommend just following what I'm doing cuz that's easiest hence, why choose it. We're going to pick the last number in the array to be the pivot.
[00:02:24] So this is the pivot. Look that's readable English good job, Brian. Okay, so this is now our pivot. So what we're going to do is we're going to construct two lists right just like we do with Mercer we did left and right, but what we're going to do is the left lists or the lesser list, however you want to call it.
[00:02:44] It's gonna be all the numbers that's smaller than six, okay? Everything is going into the right list as you might have guessed is everything is greater, right? And it doesn't matter, we put the or equal to it's long as it consistently goes to the same place. It either always goes left or always goes right.
[00:02:59] I think I always put in the left but again up to you. Okay? So in this particular case, I'm going to put everything into the left list that's smaller than 6. So I am gonna put 5 and 4, right? And then everything that goes into the right list is going to be larger.
[00:03:24] So, it's gonna be 7, 9 right? And then I'll just have this pivot here, right? Now at least all those are sort of good okay. So, going back to here.
>> Brian Holt: Not that one. Through that.
>> Brian Holt: So and then what we're gonna do is, now that we've divided into smaller lists, we're going to call Quicksort on the smaller lists, right?
[00:03:58] That's the recursive of part of this algorithm that we're gonna have. The lesser list, the greater list, and then we're gonna call Quicksort on both of those. And then essentially we're just going to trust that Quicksort's gonna do something correct and return you a sort of list and then we're going to concatenate the left list, the pivot and then the right list, right?
[00:04:19] I shouldn't gotten rid of that. Well, it's okay, actually I think I can bring it back.
>> Brian Holt: Yes, right there.
>> Brian Holt: [COUGH] So if you wanna take this further, what we're going to do is this four is going to be the pivot at this point, right? So we're gonna then call Quicksort on an empty list and then we're going to call Quicksort on five, right?
[00:04:48] So what's the base case? The base case is if you have a list of either empty or one right because that's already sorted and then so this is the base case and all it's going to do is return. So I have an empty list then I'm going to concatenate that empty list of so it's going to be empty list which is nothing then it's going to be the pivot which is four and then it's going to be five, right?
[00:05:11] Or basically this entire list right here, right? Okay, so that returns up here. So now this is sorted and so we’re gonna call Quicksort on this, right? Which as you might imagine just breaks it down into a list of 7.
>> Brian Holt: The pivot and an empty list, right?
[00:05:36] It’s like it’s nothing actually happens there, right? It's going to return 7, 9 up here. Okay and then up here now, I have 4, 5, 6, 7, 9, right? So how do I wanna do this?
>> Brian Holt: So here, I just clear this I guess.
>> Brian Holt: And say no, there we go.
[00:06:04] So I had 4,5. I had 6 and I had 7,9, right? So here, I'm gonna take the first list which is gonna be 4, 5 put in the pivot and then put in the second list.
>> Brian Holt: And that's it, that's the entire essence of what Quicksort is. Cuz you're breaking down again with the smallest, making one list, all smaller numbers one to solve the greater numbers.
[00:06:44] And then call Quicksort on those. And when it comes back, you're going to concatenate left list, then the pivot and then the right list. And so, as you may have gotten, but I haven't necessarily explicitly said, the pivot doesn't actually get passed down into either left or the right list, it just stays in that function, and then when those functions return, then it does that concatenation.
[00:07:07] But the pivot never gets passed down, the pivot just stays at that level of recursion.
>> Brian Holt: So if you come back here,
>> Brian Holt: Notice when I call so this is the pivot, 6 doesn't get passed into either one of these lists right here, right? Okay any questions conceptually about what Quicksort is doing?
[00:07:30]
>> Brian Holt: It's kind of a mess to diagram, as you can see by my chicken scratch but hopefully that makes some sense.
>> Speaker 2: Got a question.
>> Brian Holt: Yeah?
>> Speaker 2: From Mark, how do you pick a pivot when you're working with strings instead of numbers.
>> Brian Holt: How do you pick up, so the pivot is just always going to be the last one, right?
[00:07:51] Whether it's strings, objects, whatever the pivot. In this particular case, we're always going to choose the last one. We'll talk about in a second why that can possibly be a bad thing for Quicksort. But in this particular case, it works out okay.
>> Brian Holt: The question that you might be getting at in terms of strings versus numbers versus objects versus anything is you need some way to always compare, like to compare them correctly, right?
[00:08:18] So with the string usually you're thinking alphabetical order, right?
>> Brian Holt: And so the pivot is just always gonna be the last item and you're just gonna compare is this first in the alphabet or is this last in the alphabet, right? And then things that are lesser in the alphabet on the left.
[00:08:34] Things that are greater in the alphabet won't go on the right. And that's the same gist, and it works the same way, no matter if you're comparing numbers, strings, or objects, or anything, right? Yeah.
>> Speaker 2: So Drew is asking, why last instead of first?
>> Brian Holt: You can do first.
[00:08:50] It just makes the numbers work easily, 'cuz otherwise when you're doing like the math of like what index to put the right and what index to put the right. You just have to add one to everything and it's annoying. But, it doesn't actually matter what your pivots are.
[00:09:07] We just chose to last to make it easier to do, right?. We're gonna talk about Quicksort three at the end which actually does some variations on what the pivot is and that's again, when you're doing Quicksort all the variations come from choosing the pivot, right? The actual algorithm of splitting left and right that's what makes Quicksort, Quicksort.
[00:09:28] It's choosing the pivot that often ends up being the point of discussion.
>> Brian Holt: So, yeah, good question.
>> Brian Holt: But believe me, if you're doing this probably now I suggested the last any array because, it makes it simpler it makes your code simpler. I think it does.
>> Brian Holt: So let's just go through another example right here.
[00:09:56] Okay? So we have this original list of 4, 9, 3, 5. The last number is 5. So 5 has made the pivot since it's the last in the array. Then we're gonna divide into two lists, 4 and 3, right, that goes in the left list, and 9 goes in the right list, okay?
[00:10:11] And then we're gonna call Quicksort individually on each one of those. So now 3 is the pivot, so you call Quicksort on blank and 4. Those both instantly return because those are the base case of length 1 or length 0, okay? So then you concatenate empty array which is gonna do essentially nothing, right?
[00:10:30] You're gonna concatenate 3 and then you're gonna concatenate the array which has 4 in it which is going to give you 3, 4, right? That returns up, okay, so now that side's done and we're gonna work on this array which is just the base case right? It's length 1 so it just returns because it's already sorted and it's length 1.
[00:10:50] And then we're going to call concatenate on 3, 4, 5 which is the pivot, and then 9 which is going to give you 3, 4, 5, 9. Magic, right? No, it's just algorithms, awesome. Okay, any questions on that?
>> Brian Holt: Cool. So what's the big O here. Well we're still at in login.
[00:11:20] Quicksort is often faster than merge sort which is why a lot of times people tend to use it more quick like they're more apt to use that. Like for example there's lots of languages that have a Q Sort function like I think PHP has one and other languages do.
[00:11:34] Q Sort means Quicksort, right? So this is what it's doing underneath the hood. The reason why it's not necessarily always done is because it does have a bad worse case scenario. You actually can get n squared with Quicksort is just pretty rare and the reason why you can't get n squared is if you pass it a sorted list and you're always taking the last pivot, let's just diagram that real quick to see what that might look like.
[00:12:03] So if I have 1, 2, 3, 4 and I call, now we're going to say my pivot here is 4, I'm gonna end up with a list of 1, 2, 3, right? And 4 is my pivot and then blank, and then this is gonna call it Quicksort with 3 as the pivot and you're gonna end up with 1, 2, right?
[00:12:29] With the pivot here and blank over here as well, right? So, one side of the Quicksort is always going be blank, right? So that means everything is eventually going to get compared to everything which is what we're trying to avoid, right? Which is why if you pass a sorted array to a normal Quicksort, it hits its worst case scenario and it's really slow.
[00:12:55] Well, comparatively slow anyway, right? So, we'll get into a second how to solve that with choosing your pivot, but we'll talk about that after we do the exercise.