This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "Selection & Insertion Sort" Lesson
[00:00:00]
>> Bianca Gandolfo: So now we're gonna talk about Selection Sort. I'm gonna give you just a demo on how these work, and then I'm gonna set you free to pseudocode and code them out through lunch. And then we'll come back and we'll talk about solutions, your solutions, better solutions, optimizing our solutions, maybe.
[00:00:20] And we'll come and talk about our recursive. We'll introduce the recursive sorting algorithms,okay? So selection sort, what does it do? It selects the smallest element in an array and pushes it into a new array. So pretend I'm a computer, a robot. I will loop through it, my array, look for the smallest one.
[00:00:48] It's one, I will take it, pass it in to my new array. So for space complexity, this is not good, right? Because we're making a new array. This is not an in place sort. So then we look through, find the next smallest one, it's two.
>> Bianca Gandolfo: And then five.
[00:01:09]
>> Bianca Gandolfo: And then six, and then eight. So this is Selection Sort. We're literally going through the list, selecting the smallest one, pushing it on to a new array, awesome. Here's a diagram,
>> Bianca Gandolfo: Of it in place, selection sort, where we're swapping it.
>> Bianca Gandolfo: Cool, so, first selection sort in place, we're gonna look for the largest one We're going to swap it to the end.
[00:01:48] So, eight is our largest one. We're going to swap it and put five. Six, the largest one, swap it with the two. Two is our next largest one, swap it with itself. One, swap it with itself. Or perhaps we can optimize there, that would be optimizing for adaptability.
[00:02:15]
>> Bianca Gandolfo: All right? Selection sort, not in place, in place,
>> Bianca Gandolfo: Which is better, one takes less space. If that matters to you, you probably wanna have the in place one. If it doesn't and,
>> Bianca Gandolfo: Then do the easier one.
>> Speaker 2: Is the time complexity the same?
>> Bianca Gandolfo: Was the time complexity the same?
[00:02:37] Yeah, the time complexity of all of these are the same basically, yeah, and squared. So Insertion Sort is another elementary sort, and this is the third and last sort. And you're gonna implement all of these and get super familiar with them. So you're gonna select the first element in the array, you're gonna push it into a new array.
[00:02:57] And as you go through the original array, you're going to either put it before or after, in order, in the second array. Are you guys seeing the difference between these?
>> Speaker 2: So then in selection you would grab one and then you would grab two and this you would grab one and then you would grab six.
[00:03:17]
>> Bianca Gandolfo: Yep, so we do one and then we take it out right. So pretend that's gone. Then we have six. Six is are greater, so we put it after. And we have eight. Eight greater than one yes, greater than six yes. And we'll put it after eight, two, two greater than one, yes, greater than six no, awesome.
[00:03:39] Five greater than one yes, greater than two, greater than six no.
>> Bianca Gandolfo: That's insertion sort.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: Questions about this?
>> Bianca Gandolfo: Here's another diagram.
>> Bianca Gandolfo: Insertion Sort in place, how do you think this is gonna happen? Don't read it. Of course, [CROSSTALK]. Someone to read it to me?
[00:04:15] Suddenly I forgot how to read.
>> Speaker 2: Selects the first element in an array, considers that our sorted list of size one. As each new element is added, insert the new element in the correct order by swapping in.
>> Bianca Gandolfo: Yeah, so we start here. We have our sorted list of one.
[00:04:36] We add six. We say, is six greater than our original sorted list? Yes, so we'll just keep it there. Then we add eight. And we say, is eight greater than one? Yes, is eight greater than six? Yes, and then we put it in our sorted list of three.
[00:04:52] Etc, just like in other one, except that there will be swapping.
>> Bianca Gandolfo: Yes, clear? Because you're gonna have to be coding this in a second, literally a second.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: So Christine is asking, what's the time complexity of Insertion Sort and Selection Sort? I wanna tell you and I kinda hinted at it, but I want you to code it out and calculate it yourself.
[00:05:24]
>> Speaker 3: Pseudo code first, right?
>> Bianca Gandolfo: Yep, pseudo code it, and then you're gonna code it out. And that's gonna be in the exercises here.
>> Bianca Gandolfo: But do we have any other questions before we hop to the exercises?
>> Bianca Gandolfo: No.
>> Speaker 4: Can you repeat one more the, kind of we put one more the, the first step, this acoustic examples you gave us.
[00:05:49]
>> Bianca Gandolfo: Which example?
>> Speaker 4: Five can be in.
>> Bianca Gandolfo: Which one? You have to talk a little bit louder.
>> Speaker 4: Sorry, that example using Bike A, Bike C,
>> Speaker 4: At the beginning.
>> Bianca Gandolfo: Tell me when,
>> Bianca Gandolfo: This one?
>> Speaker 4: This one, Stability.
>> Bianca Gandolfo: What's your question?
>> Speaker 4: My question is the second one.
[00:06:15] Give equal price, I want lighter option. It's the idea.
>> Bianca Gandolfo: So you have to talk a lot louder, I can't hear you.
>> Speaker 4: Given equal price, just that last, I want our option to be first that idea.
>> Bianca Gandolfo: Which one do you want to be first?
>> Speaker 4: Just kindly would repeat again, your explanation?
[00:06:40]
>> Bianca Gandolfo: Yeah, sure, I can reexplain it for sure. So, this is an example of stability which is something you might consider when choosing a sorting algorithm or you might consider adding this to an algorithm that you're writing. And it's important when you want to preserve the original order of a list.
[00:06:58] So say for example, trying to think of a different example other than these bikes. But let's say, for example, you first sort your hotels on Kayak.com. You sort it first by rating. And so we have the top rating first. And then, you want to sort it by price.
[00:07:19] And so, what you want is, at the end of the day is to have the first one to be the highest rating, maybe for the lowest price. Does that make sense? And so that would be an example of why you'd want stability in your search, is when you have it in a certain order that you wanna preserve even when you resort it, when the prices are the same.
[00:07:42] Or when the sum value is the same. So for this example of the bikes, BIke B and Bike C are both $500. It's originally sorted here, right. So it's sorted by weight in ascending over. So heavier is at the bottom, with lighter at the top. When we resort it for price, this is the original sorted order for weight.
[00:08:10] This is the new sorted order for price where when the price is the same, it's gonna keep the same order. So if you notice Bike B comes before Bike C here.
>> Bianca Gandolfo: When here it's also the same, right? Bike B also comes before Bike C, that's useful. But that's not always guaranteed in all of our source that this is gonna happen.
[00:08:35] Does that make sense?
>> Speaker 3: That's because Bike B is less than, I mean weighs less than Bike C, right?
>> Bianca Gandolfo: Yes, but the point here is, maybe where we take this for granted when we're sorting things in our mind. But you might have to explicatively tell your algorithm to do this.
[00:08:51] Or it might just do it in whatever order. It might swap them. So just be mindful of your swaps.
>> Speaker 5: On Kayak if you don't do it, you'll get all the lower priced hotels that [INAUDIBLE] grading, so you might be in a flea-bitten, best western somewhere.
>> Bianca Gandolfo: Yeah.
[00:09:12]
>> Group: [LAUGH].
>> Bianca Gandolfo: Best eastern.
>> Speaker 5: Best eastern [LAUGH].
>> Bianca Gandolfo: Yeah, so the next question is, how can we make an algorithm adaptive? So I mentioned before that it depends on the algorithm. And some of them are adaptive, and some of them aren't. And some of them you can put breaks and things, to make it more adaptive.
[00:09:37] So we'll talk about it specific case by case. How to make a specific algorithm more adaptive or not. And you can think about it as you're writing out your procedures. What if, you know, what if we only get half way through sorting this and its already sorted, what happens?
[00:09:54] How do we know that? So for some of them you might be able to track if you're swapping like maybe if you loop through entire list and you don't swap, you can flag that. That means it's sorting. That's one example, but it depends on the algorithm, yeah.