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.

Insertion Sort

Learn to Program: Crafting Quality Code

Meet the Instructors