Trying to understand insertion sort algorithm

Question

I'm reading some books on Python, data structures, and analysis and design of algorithms. I want to really understand the in's and out's of coding, and become an efficient programmer. It's difficult to ask the book to clarify, hence my question on stackoverflow. I'm really finding Algorithms and recursion challenging ... I posted some code (insertion sort) below that I'm trying to understand exactly what's happening. I understand, generally, what is supposed to happen, but I'm not really getting the how and why.

From trying to analyze pieces of the code on Python Idle, I know that:

key (holds variables) = 8, 2, 4, 9, 3, 6

and that:

i (holds the length) = 7 ( 1, 2, 3, 4, 5, 6, 7)

I don't know why 1 is used in the first line: range(1, len(mylist)). Any help is appreciated.

mylist = [8, 2, 4, 9, 3, 6]

for j in range(1,len(mylist)):
    key = mylist[j]
    i = j
    while i > 0 and mylist[i-1] > key:
        mylist[i] = mylist[i - 1]
        i -= 1
        mylist[i] = key

Answer 1

Let me try to break this down.

Start by considering a list. It is "almost" sorted. That is, the first few elements are sorted, but the last element is not sorted. So it looks something like this:

[10, 20, 30, 50, 15]

Obviously, the 15 is in the wrong place. So how do we move it?

    key = mylist[4]
    mylist[4] = mylist[3]
    mylist[3] = key

That'll switch around the 15 and the 50 so now the list looks like:

[10, 20, 30, 15, 50]

But we'd like to do this several times in a loop. To do that we can do:

while ???:
    key = mylist[i]
    mylist[i] = mylist[i-1]
    mylist[i-1] = key
    i -= 1

That loop will go back one position at a time swapping the two elements. That'll move the out of order position one place back each time. But how do we know when to stop?

Let's look again at our list and the moves we want to make:

[10, 20, 30, 50, 15]
[10, 20, 30, 15, 50]
[10, 20, 15, 30, 50]
[10, 15, 20, 30, 50]
# stop! we are sorted now!

But what is different that last time around? Every time we move the number one place back, it is because the 15 is less then the element on the left, meaning its not sorted. When that is no longer true we should stop moving. But we can easily deal with that:

key = mylist[i]
while key < mylist[i-1]:
    mylist[i] = mylist[i-1]
    mylist[i-1] = key
    i -= 1

Ok, but happens if we now try to sort this list:

[10, 20, 1] [10, 1, 20] [1, 10, 20] # ERROR!!

At this point something bad happens. We try to check whether key < mylist[i-1] but when we've reached the beginning, i = 0, and this checks the end of the list. But we should stop moving to left at this point...

If we reach the beginning of the list, we can't move our pivot/key further so we should stop. We update our while loop to handle that:

key = mylist[i]
while i > 0 and key < mylist[i-1]:
    mylist[i] = mylist[i-1]
    mylist[i-1] = key
    i -= 1

So now we have a technique for sorting an almost sorted list. But how can we use that to sort a whole list? We sort parts of the list at a time.

 [8, 2, 4, 9, 3, 6]

First we sort the first 1 elements:

 [8, 2, 4, 9, 3, 6]

Then we sort the first 2 elements:

 [2, 8, 4, 9, 3, 6]

Then we sort the first 3 elements

 [2, 4, 8, 9, 3, 6]

So on and so forth

 [2, 4, 8, 9, 3, 6]
 [2, 4, 8, 9, 3, 6]
 [2, 3, 4, 8, 9, 6]
 [2, 3, 4, 6, 8, 9]

But how do we do we do that? With a for loop

for j in range(len(mylist)):
    i = j
    key = mylist[i]
    while i > 0 and key < mylist[i-1]:
        mylist[i] = mylist[i-1]
        mylist[i-1] = key
        i -= 1 

But we can skip the first time through, because a list of one element is obviously already sorted.

for j in range(1, len(mylist)):
    i = j
    key = mylist[i]
    while i > 0 and key < mylist[i-1]:
        mylist[i] = mylist[i-1]
        mylist[i-1] = key
        i -= 1 

A few minor changes which make no difference brings us back to your original code

for j in range(1, len(mylist)):
    key = mylist[j]
    i = j
    while i > 0 and key < mylist[i-1]:
        mylist[i] = mylist[i-1]
        i -= 1 
        mylist[i] = key

Answer 2

The insertion sort algorithm works by trying to build up a sorted list of increasing length at the start of the array. The idea is that if you start off by building a one-element sorted list at the beginning, then a two-element list, then a three-element list, etc., that once you've built up an n-element sorted list, you have sorted the entire array and are done.

For example, given the array

3  1  4

We can split this into a zero-element sorted list and a three-element unsorted list:

| 3  1  4

Now, we add 3 to our sorted list. Since that list is now only one element long, it's automatically sorted:

3 | 1  4

Now, we want to add 1 to our sorted list. If we just add 1 to the end of the list like this:

3 1 | 4

then the sorted list is no longer sorted. To fix this, the inner loop of the insertion sort code works by continuously swapping the 1 with the element before it until it's in the proper position. In our case, we swap the 1 and the 3:

1 3 | 4

and since the 1 is now at the beginning of the array, we don't need to move it any more. This is why the inner loop runs while i > 0; once the index of the new element (i) is at the start of the array, there's nothing before it that could be any bigger.

Finally, we update the array by adding 4 to the sorted list. Since it's in sorted position, we're done:

1 3 4

And our array is now in sorted order.

Now, to your original question: why does the outer loop start at 1? This is a cute optimization trick. The idea is that any one-element array must automatically be sorted. This means that the algorithm can start off by saying that the first element of the array is a one-element sorted list. For example, given the array

2  7  1  8

The insertion sort algorithm could try splitting this array like this, putting an empty sorted list at the front:

| 2  7  1  8

But a marginally faster option is to split the list like this:

2 | 7  1  8

which is guaranteed to be safe because any one-element list is automatically sorted.

This is really an optimization of the algorithm on the part of the authors. The algorithm would work perfectly fine if the outer loop started at zero, but they've just decided to start it at one to avoid an unnecessary loop iteration.

Hope this helps!

Answer 3

Have a look at the while loop. It starts with i having the value of 1, but then i is decreased. So in the last line, the minimum value of i could be 0, which is the first element in the list. If you would start with 0, i would become -1 which is valid in python, but means the last element. Therefore the range has to start with 1.

I would like to mention, that you are asking for insertion sort. I don't thin that your code implements insertion sort. Looks rather like bubble sort or something like that.

Answer 4

The reason is that:

i = j

and that mylist is accessed like:

mylist[i - 1]

Therefor the first value is 0. If the range would have started at 0, it would cause an mylist to be accessed at position -1.