Original subtitles

‫This algorithm lesson we're going to discuss the insertion sort out with them the insertion sort.

‫Is one of the most basic sorting algorithms out there.

‫And it's nice because it's incredibly easy to understand it's also pretty easy to implement when it

‫comes to sorting algorithms.

‫It does have some weaknesses.

‫If you have a dataset you're trying to sort that is a has a lot of integers or a lot of different items

‫and an insertion sort is definitely not the best one to go with.

‫However if you're looking for a smaller number of items it works very well.

‫It's also very for if you're just trying to get to learn and sorting and algorithms.

‫So we're going to start with this array and it has six elements.

‫5:47 twelve hundred thirty three and 21.

‫And so what we're going to do is go through each one and then get through the stages of what it takes

‫to sort this using the insertion sort algorithm.

‫So what you do is you start off on the left hand side.

‫And so we're going to look at the integer 5 and what the first step is comparing five and 47.

‫We see that 500 and 47 are already in sorted order so that's good.

‫That means that we don't have to do anything with these.

‫So are the first set of the iteration actually remains the same.

‫Then we go onto the third item which is 12 when we do a comparison and we say is 47 less than or equal

‫to 12 or you can say is 12 less than or greater than 47.

‫And we know 12 is less than.

‫And so what we're going to do is take 12 and move it right here.

‫So the next version of the store would be four five 12 forty seven hundred thirty three and 21.

‫So we now are sorted for the first three items.

‫Next thing we do is we look at the fourth item and we compare it to 47.

‫We realize 100 is greater than 47.

‫And so we don't have to do anything at all.

‫So the first four items are sorted.

‫Next we look at 33 in and we see is 33 less than 100.

‫We know it is so we say OK what is 33 less than 47.

‫Yes it does.

‫So we know 33 has to go here.

‫There's actually one other step in here I shouldn't let go.

‫We actually have to compare 33 to 12.

‫So that would be the real step.

‫You know just using common sense you can see where it would go.

‫But in the real life algorithm it what you would do is you take 33.

‫Compare it with each item to the left until it was greater than one of the items then you would just

‫keep on moving.

‫So the next version would be five twelve thirty three forty seven and 100 and for the last word and

‫then 21 for the last version we know we have five 12:33 47 and 100 are all sorted.

‫So for the last one we take 21 and we compare it to 100.

‫We know it's less than 100 compared to 47.

‫We know it's less than 47.

‫We compared to 33 it's still less than 33 we compared to 12.

‫We see it's more than 12.

‫So we know it goes right here.

‫And so for the last iteration we know it's five 12 21 33 47 and 100.

‫And so there you go you have a fully sorted list.

‫Now when you're dealing with six items this is absolutely fantastic algorithm to use when you get to

‫you know larger items you know over a thousand items or anything like that.

‫Then this is going to be really good.

‫This is essentially brute force type algorithm and so you're looking at every element and then you're

‫moving that element based on its balance.

‫We're going to get into some other algorithms such as mergesort and quicksort which are a lot more intelligent.

‫They have some pretty powerful mechanisms that make them perform much better and operate much faster

‫exponentially faster actually.

‫And so if you want to know the time complexity which if you're taking this for an algorithm class or

‫something like that and you definitely want to know the time complexity this actually had three different

‫complexities.

‫We have our best case.

‫We have our average and we have our worst

‫it's really good to know all three because with all three you're going to get different values.

‫Best case is actually going to the order of an average and worst are going to be the same.

‫They're going to be order in squared and order of squared.

‫Now if you watched my video talking about growth of functions you know that anything on this side of

‫the world is really a first especially for sorting is not a great way to go because these numbers get

‫very fast very quickly and you'll end up having some very slow poor performing type of programs so we

‫want to stay away from this for large items.

‫However the interesting thing is this best case this best case is actually better than some of the most

‫powerful algorithms out there.

‫Some things that are used for just gigantic applications this little insertion sort of rhythm actually

‫works better than those in certain cases.

‫And if you want to know that case it's actually important to think about it because if you really understand

‫now over them it'll make perfect sense.

‫If you notice how many times we had to iterate here we create a new list each time we went through but

‫we only have to do that when the item the next item down the list was less than the item to the left

‫when that wasn't the case.

‫Were able just to move right on to the next item.

‫So take for example five 2:47 we saw that 5 was already less than forty seven.

‫We didn't have to do anything.

‫We just continued right on to 12.

‫Now imagine if our list started out as 5 12 21 33 47 and 100.

‫In other words if we got a list that was already sorted it was already in sorted order.

‫That's when we would get this best case and the order of n just means that the speed or the time complexity.

‫All it takes is the amount of time it takes to get through the total number of items in the list.

‫And so that's incredibly fast.

‫The some of the other fast algorithms typically have a time complexity in law again which has a speed

‫that is actually rate right in this area in between these two type of complexities and the reason for

‫this is because the insertion sort is so basic it doesn't have a lot of different things like It doesn't

‫have a lot of big mathematical functions it doesn't do divide and conquer it's actually pretty basic

‫in how you implement it.

‫And so if you have a list of items that you know is either in order or it's very close to being in order.

‫A great example I heard is say that you are making a baking application and that 90 plus percent of

‫the items that you're getting for check numbers for the most part those are going to be either in order

‫as your application receives them or it's going to be very close to being in order insertion sort would

‫actually be a pretty good algorithm for that because when it takes items that are in order even a large

‫number of them it does very well with that because it only has to do it's more time consuming kind of

‫functions when it's having.

‫You know when it's actually moving the items in the array.

‫And so for Best case you can get to this if you know that you're dealing with data that is very close

‫to being sorted and you just kind of want to polish up the array to make sure it's in perfect sorted

‫order.

‫That's when you can use that.

‫Or if you're dealing with a very small number of items.

‫Worst case right over here the very worst case you could ever get on this was if the items were in reverse

‫sorted order and if you want to know the reason for that.

‫I mean just give us a little bit of room up here and just clean this up.

‫The reason for that is because if you're trying to get these all in the correct sorted order Michael

‫and I'll keep that right here.

‫You look at each item and you compare it with the item on the left.

‫Now what would happen if we had this in reverse sorted order 3 21 12 and 5 we would literally have to

‫create a new line for every single version so we have to create one that was forty seven hundred thirty

‫three 21 12 and 5 and then the next one we would have to do the exact same thing over and over and over

‫and over again.

‫And so you would have to go through the entire list and you'd have to iterate through every item where

‫you're essentially taking this hundred moving through each item until it's at the end.

‫Then you take the 47 and you do you'd be doing the exact same process.

‫So if you have something in reverse sorted order it or something in that side of the world insertion

‫sort is an absolutely horrible algorithm to use.

‫So you have to make sure that you do know the type of data that you're dealing with that's important

‫in any type of application.

‫But especially if you're working on sorting knowing your dataset is very important so please let me

‫know if you have any questions at all about insertion sort.

‫And I'll see in the next video.