Four Semesters of Computer Science in 5 Hours Exercise 5 Solution

[00:00:00]
>> [MUSIC]

[00:00:04]
>> Brian Holt: So, let's go ahead and do quick sort together. Did anyone get it in here by the way? Awesome.
>> Brian Holt: Cool, let's take a look at it.
>> Brian Holt: And if you didn't again remember this is hard, right. This is why they ask in interviews, so it weeds out people that haven't read a book before or something like that, I don't know.

[00:00:32] That's probably really mean to say. No, people that just haven't gone through this stuff that, because obviously you don't encounter it on your day to day, right? That's not what I intended to say, not to be the raging jerk that I just was. Okay Hans, I'm really sorry.

[00:00:48] So, let's create a new function called Quicksort. Okay, so we know this is a new cursive function, so what's the first thing we do? Base case I keep repeating this because it's super important.
>> Brian Holt: So, let's do if nums.length is less than or equal to 1 then just go ahead and return whatever is in nums.

[00:01:13] That's totally fine, okay? So, this says if we have a length 1 length 0 then you can just go ahead return just that because it's already sorted, okay? So, first thing, let's find the pivot. The pivot we know is always going to last one. So, we're gonna say const pivot = nums, nums.length-1, right.

[00:01:37] This is gonna be the last element of the array. They're gonna create new two new arrays const left equals empty array, const right equals empty array, okay
>> Speaker 2: Those can't be consts can they?
>> Brian Holt: Those need to be. They can be consts.
>> Speaker 2: You're not reassigning.
>> Brian Holt: Exactly, so a little bit confusing, those can be consts because we're not actually.

[00:02:04] If you want to think about it in terms of pointer, we're not moving the pointer, right? So, this is different than object.freeze. So that's one thing to keep in mind.
>> Brian Holt: I know other people that feel this way, if you feel better about putting the let here because you're saying, I'm going to be making this mutable that's fine too.

[00:02:27] Whatever communicates to you better. That's what all this is about because you're not really getting performance gains here. Okay, so if we're gonna make a for loop that we're going to loop over and just divide into two lists, okay? So let i = 0, i < nums.length i++, right?

[00:02:51] Nothing too crazy there, and then we're just gonna ask simply is if nums up, i < pivot, then left.push(nums[i]), right? Else what. Well, if it's not going in the left one, it's definitely going in the right one. So, right.push(nums[i]).
>> Speaker 2: Aren't you pushing the pivot onto those two at this point?

[00:03:23]
>> Brian Holt: We're not gonna be pushing the pivot at all. The pivot doesn't get pushed into either side.
>> Speaker 2: How do you avoid that scenario?
>> Brian Holt: You're absolutely right, you need to do -1. I missed that part because you don't actually wanna go all the way to the end.

[00:03:46] Good call. Okay, so, now we have two lists, right? And again, if you feel more comfortable saying const sortedLeft = quickSort Left, that's totally fine with me to do. I'm just gonna do it the short way. I'm just gonna return a new array [ ...quickSort(left), then so we're gonna have the left array right?

[00:04:20] And then we're gonna have to pit it. And then we're going to have quickSort. Sorry, again right, now since we know both these are going to return a raise every single time. That's totally kosher to do. But, If you want this, make a little bit maybe more familiar you can say, you can do left dot concat.

[00:04:57] Sorry, quick sort left rather.
>> Brian Holt: You can do it this way and then do pivot quicksort right. Right, any one of these is gonna work. You cans separate it out to different calls if you want to. You can do dot concat, and so making a new array every single time.

[00:05:20] That works too. All that totally works.
>> Brian Holt: This is programming, there's a bunch of different ways to write it, so. In this particular case we're gonna stick with that cuz I think it looks pretty cool.
>> Brian Holt: And okay, so let's just make sure I didn't mess anything up

[00:05:44]
>> Brian Holt: And it works.
>> Brian Holt: Any questions?
>> Brian Holt: I felt like someone wanted to say something and then gave up. [LAUGH] Great.
>> Speaker 2: We should just use pop instead of doing that nums.length- 1. That feels kinda weird.
>> Brian Holt: So pop.
>> Speaker 2: So like pivot equals nums.pop Not just
>> Brian Holt: Yeah, you could.

[00:06:18] So, the reason why one might not want to do that which I haven't been doing on other places but one could do here is now you're being destructive to nums. So, whatever they're passing in it gets modified and often that's not desirable and we're going to get into that later of why that's not desirable but it would be totally right that insertion sort and bubble sort were destructive.

[00:06:42] So,
>> Brian Holt: Yeah, I try not to be destructive when I don't have to be.
>> Brian Holt: It's a good question though. The answer is it still works, so, to your point it does still work.
>> Brian Holt: Great, well congratulations. We have done all the sorting that we're gonna do today, and I'm gonna say that those are the heavy hitters in the sorting world.

[00:07:12] There's some other ones people use like radix sort which is crazy [INAUDIBLE] that's were not gonna talk it cuz I don't understand it super well. There's selection sort which is like an intermeric- intermediary step between bubble sort and insertions sort. I don't think anyone really uses selection sort either.

[00:07:31] It's just another one of those instructive ones I have a personal favorite which is called Bogosort. And, Bogosort just imagine you have a deck of cards that you wanna sort. With Bogosort what you do is you throw them all up in the air and then you pick them up and then you see if they're sorted.

[00:07:46] And if they're not then you throw them up in the air again and you pick them up and you see if they're sorted. I don't know someone, it's a real thing. I'm gonna prove it to you right now. Bogosort Wikipedia.
>> Brian Holt: It's a particularly ineffective sorting algorithm. [LAUGH] Thank you, Wikipedia.

[00:08:10] Also called stupid sort. I like that. Anyway there's another one that's really funny. It's average cases n plus one factorial, which is a huge number. So, there's another reason we didn't do that one, because it takes forever for it to work.