Hello YouTube, and welcome back to Sorting Algorithms!
Please watch Episode 1 if you haven't done so. It will give you a clearer understanding of the concepts behind sorting in general.
Now, in this episode we cover the Insertion sort.
this sorting algorithm is pretty different from the ones we've seen so far
Instead of running through a list again and again, by the time the algorithm reaches the last item in the list, it is sorted for sure.
You see, the idea is that the algorithm will split a list into two parts
The first part is considered sorted among itself.
The algorithm will then pick an item and move it backwards over the sorted region
and place it in the appropriate slot, such that the sorted region remains sorted.
Confused? Probably.
Just watch the demonstration.
Here we have our unsorted list. Take note that insertion sort starts on the second item.
The first item will automatically form the first item in the sorted region.
So, for illustration purposes we'll color the items in the sorted region blue.
Since "5" is in that region, I'll color it blue.
The algorithm picks out "4" now, and will attempt to slot it into the sorted region.
Since the only item in there is "5", and "4" is smaller than "5"
it is moved before "5", and inserted back into the list. We'll color it blue.
The algorithm now picks out "6". Notice that, everytime the computer is processing a particular item
all the items before it form the sorted region.
We attempt to place "6" in the sorted list.
Since it is not smaller than "5", it cannot be placed anywhere before it.
Notice that, even though there is more than one item in the sorted region
insertion sort only needs to make one comparison - That's because the items in the sorted region are, well, sorted.
So the algorithm can be sure that, if "6" is larger than the last item in the sorted region
there is no need for further comparison, since there is no chance of encountering a larger value in that region.
Since "6" doesn't need to move, it is inserted back where it was.
We turn it blue since it now forms the sorted region.
The algorithm now picks out "1".
It is smaller than 6,
smaller than 5,
and also smaller than 4.
Since we've gone through the entire sorted region,
it's space must be all the way at the head of it.
We drop it in place, and now it forms yet another item in the sorted region.
We pick out "2", and the process repeats.
Notice that "2" is larger than "1", but smaller than "4".
To keep the region sorted, it's proper place is where the empty slot is.
"2" is inserted into the space.
We move on to "3". Once again, it fits between "2" and "4", and is thus inserted there.
"7" behaves the same way as what happened earlier with "6"
It doesn't need to move anywhere, so it is put in place.
Notice how the sorted region has grown and grown - and now covers the entire list. Hence, the list is sorted.
In terms of efficiency, insertion sort doesn't do very well according to the Big O Notation,
faring with a time complexity of n².
While it does indeed finish sorting everything in a single pass
during this time it still needs to move backwards in the list
taking up processing time.
Insertion sort, like bubble sort, works best if a list is already partially sorted.
That's all there is for today, thank you for following this series
I'll see you in the next episode. You're watching 0612 TV.
