[Insertion Sort]
[Tommy MacWilliam] [Harvard University]
[This is CS50.TV]
Let's take a look at insertion sort, an algorithm for taking a list of numbers and sorting them.
An algorithm, remember, is simply a step-by-step procedure for accomplishing a task.
The basic idea behind insertion sort, is to divide our list into two portions,
a sorted portion and an unsorted portion.
>> At each step of the algorithm, a number is moved
from the unsorted portion to the sorted portion
until eventually the entire list is sorted.
Here is the list of six unsorted numbers--23, 42, 4, 16, 8, and 15.
Since these numbers are not all in ascending order, they're unsorted.
Since we haven't started sorting yet, we'll consider all six elements our unsorted portion.
>> Once we start sorting, we'll put these sorted numbers to the left of these.
So, let's start with 23, the first element in our list.
We don't have any elements in our sorted portion yet,
so let's simply consider 23 to be the start and end of our sorted portion.
Now, our sorted portion has one number, 23,
and our unsorted portion has these five numbers.
Let's now insert the next number in our unsorted portion, 42, into the sorted portion.
>> To do so, we'll need to compare the 42 to the 23--the only element in our sorted portion so far.
Forty-two is larger than 23, so we can simply append 42 to the end
of the sorted portion of the list. Great!
Now our sorted portion has two elements, and our unsorted portion has four elements.
So, let's now move to the 4, the next element in the unsorted portion.
So, where should this be placed in the sorted portion?
>> Remember, we want to place this number in sorted order
so our sorted portion remains correctly sorted at all times.
If we place the 4 to the right of the 42, then our list will be out of order.
So, let's continue moving right-to-left in our sort portion.
As we move, let's shift each number down a place to make room for the new number.
Okay, 4 is also less than 23, so we can't place it here either.
Let's move the 23 right one place.
>> That means we'd like to place the 4 into the first slot in the sorted portion.
Notice how this space in the list was already empty,
because we've been moving sorted elements down as we've encountered them.
All right. So, we're halfway there.
Let's continue our algorithm by inserting the 16 into the sorted portion.
Sixteen is less than 42, so let's shift the 42 to the right.
Sixteen is also less than 23, so let's also shift that element.
>> Now, 16 is greater than 4. So, it looks like we'd like to insert the 16 between the 4 and the 23.
While moving through the sorted portion of the list from right to left,
4 is the first number we've seen that is smaller than the number
we're trying to insert.
So, now we can insert the 16 into this empty slot,
which, remember, we've created by moving elements in the sort portion over
as we've encountered them.
>> All right. Now, we have four sorted elements and two unsorted elements.
So, let's move the 8 into the sorted portion.
Eight is less than 42.
Eight is less than 23.
And 8 is less than 16.
But 8 is greater than 4.
So, we'd like to insert the 8 between the 4 and the 16.
And now we just have one more element left to sort--the 15.
Fifteen is less than 42,
Fifteen is less than 23.
And 15 is less than 16.
But 15 is greater than 8.
>> So, here is where we want to make our final insertion.
And we're done.
We have no more elements in the unsorted portion,
and our sorted portion is in the correct order.
The numbers are ordered from smallest to largest.
So, let's take a look at some pseudocode that describes the steps we just performed.
>> On line 1, we can see that we'll need to iterate over each element in the list
except the first, since the first element in the unsorted portion will simply become
the first element in the sorted portion.
On lines 2 and 3, we're keeping track of our current place in the unsorted portion.
Element represents the number we are currently moving into the sorted portion,
and j represents our index into the unsorted portion.
>> On line 4, we're iterating through the sorted portion from right to left.
We want to stop iterating once the element to the left of our current position
is less than the element we're trying to insert.
On line 5, we're shifting each element we encounter one space to the right.
That way, we'll have a clear space to insert into when we find the first element
less than the element we're moving.
On line 6, we're updating our counter to continue to move left through the sorted portion.
Finally, on line 7, we're inserting the element into the sorted portion of the list.
>> We know that it's okay to insert into position j,
because we've already moved the element that used to be there one space to the right.
Remember, we're moving through the sorted portion from right to left,
but we're moving through the unsorted portion from left to right.
All right. Let's now take a look at how long running that algorithm took.
We'll first ask the question how long does it take for this algorithm to run in the worst case.
Recall that we represent this running time with Big O notation.
In order to sort our list, we had to iterate over the elements in the unsorted portion,
and for each of those elements, potentially over all elements in the sorted portion.
Intuitively, this sounds like an O(n^2) operation.
>> Looking at our pseudocode, we have a loop nested inside another loop,
which, indeed, sounds like an O(n^2) operation.
However, the sorted portion of list didn't contain the entire list until the very end.
Still, we could potentially insert a new element at the very beginning of the sorted portion
on every iteration of the algorithm,
which means that we'd have to look at each element currently in the sorted portion.
So, that means we could potentially make one comparison for the second element,
two comparisons for the third element, and so on.
So, the total number of steps is the sum of the integers from 1 to the length of the list minus 1.
We can represent this with a summation.
>> We won't go into summations here, but it turns out that this summation is equal to
n (n - 1) over 2, which is equivalent n^2/2 - n/2.
When talking about asymptotic runtime,
this n^2 term is going to dominate this n term.
So, insertion sort is Big O(n^2).
What if we ran insertion sort on an already sorted list.
In that case, we'd simply build up the sorted portion from left to right.
So, we'll only need on the order of n steps.
>> That means that insertion sort has a best-case performance of n,
which we represent with Ω(n).
And that's it for insertion sort,
just one of the many algorithms we can use to sort a list.
My name is Tommy, and this is CS50.
[CS50.TV]
Oh, you just can't stop that once it starts.
Oh, we did that-- >>Boom!