All language subtitles for 3 - Insertion Sort English

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.