0:00
One approach to solving the sorting problem is to use the insertion sort
algorithm. That's what this lecture is all about.
We call from selection sort, the state of the list at the beginning after some
passes, and at the end. The same is true for insertion sort.
At the beginning, the entire list is unsorted and i refers to zero.
After some passes have been completed, part of the list is sorted and part is
not. I refers to the index of the first item
in the unsorted part of the list. At the end, the entire list is sorted,
and i refers to the length of the list. For insertion sort, one pass at the
algorithm involved taking the item at index i and including it in the sorted
section of the list. Let's look at an example.
Since the entire list is still unsorted, adding i to the sorted part of the list
is simple. We just increment i and move on to the
next pass. The 7 is compared with the 3, and since 7
is greater than 3, it's in its correct position.
Next, the two needs to be include din the sorted part of the list.
We know that the 5 will be in the same position as it was before.
In any given pass, only the items from index zero up to and including index i,
might change. 2 is less than seven, and it's less than
three, so the two belongs at index zero. The 7 will be removed over one position,
and the three will be moved over a position, making room to put the two at
index zero. Now let's try for the fourth pass.
The element index I the fourth path, the element index by five needs to be
included in the sorted parts lists. 5 is less than 7 and it's greater than 3,
so the 7 shifted to the right in the 5 is inserted at index 2.
Let's implement this algorithm. For each pass through the algorithm the
item at index i is inserted into the sorted part of the list.
The insert function is a helper function that we'll now write.
The variable value will refer to the list at index i, which is the item to be
inserted into the sorted cards list. Next, we need to find the index j, where
the value belongs. We also need to make room for the value
by shifting. And once we know the index where the
value belongs, index j, we need to put the value there.
Finding the index and making the room is the trickiest bit.
For now, we'll leave the y loop condition unspecified and we'll add it in a moment.
In the body of the loop, one item will be shifted to its right, the index j, is
then decreased by 1. To determine the loop condition, let's
revisit our example. Initially, j refers to i, 2 is compared
with 7, and because it's less than 7, the 7 will be shifted to the right.
Then the value of j will be decreased. Next, 2 is compared with 3, and the 3 is
shifted to the right, then the value of j is decreased again.
At this point j refers to zero, it's not possible to go any further to the left.
We've found the location where the two belongs.
Let's add this reason for stopping to the [UNKNOWN] loop condition.
We want to stop when j is equal to zero, so we'd like to continue as long as it's
not. There's another reason why the loop might
end as well. Let's consider a second example.
In this case, 5 is compared with 7, and 7 is shifted to the right.
The value of J is decreased. Next 5 is compared with 3, and because
it's bigger than 3 we stop. We stop when the list at j minus 1 is
less than or equal to the value, so the second condition under which our wild
loop should continue is that l at j minus 1 is greater than the value.
Now, that we've finished the implementation, let's run the doc test.
The test passed.