Insertion sort

Here is the insertion sort algorithm:

The insertion sort is a loop. We need to do the loop the same number of times as there are piles of sticks. This is the length of the "gamestate" list. You can find this length with "len(gamestate)". We want a loop for which a variable (called "i" in the rest of this Q&A file entry) goes from 0 up to this length, not including the length itself. That is, we will examine all elements of the list, by using "gamestate[i]".

And what do we do for each element of the list? We figure out where it goes, out of the list so far. The idea is that after the loop executes a certain number of times, call it 'n', then items 0 through n-1 inclusive will be in order. So for example after the loop has iterated 5 times, for i being 0, 1, 2, 3, and 4, then items 0 through 4 (inclusive) will be in order. So the next time around the loop, when i is five, we just have to figure out where the old gamestate[5] belongs in the list so far, and after this, items 0 through 5 inclusive will be in order. And we keep doing this until we have gone through the whole list.

At the beginning, when i is 0, we can be confident that all the previous items are in order -- there aren't any of them. We will then end up picking 0 as the proper location for gamestate[0]. Don't worry about this beginning bit too much. If you write your loop body assuming the typical case, you will probably find it also works for the beginning case.

So, the loop body has to do two things: First, find where the item should go; second, move it there.

To do the first bit, you need another loop, inside the main loop. The main loop will be a 'for' loop, but I think you'll find this easier if it's a 'while' loop.

Let's lead up to this gradually. First, consider the following for loop. We'll use the variable "where", which is going to end up being where to insert this list item. But first, just the loop structure.

for where in range(i):
    print i

That is equivalent to the following 'while' loop:

where = 0
while where < i:
    print i
    where = where + 1

Obviously, the 'while' loop has disadvantages -- it's more complicated to write, easier to make a mistake. We prefer the 'for' loop most of the time.

But this 'while' loop has some advantages too. First of all, 'where' continues to exist after the loop. It will have the value of i after the loop is over. Second, we can make the 'while' condition more complicated. Instead of just saying "where < i", it can say where<i and some other conditions.

So you can write a loop like that which continues until it finds a location which is where the item should be inserted; or ends up coming out of the loop because where is no longer less than i, which will be when it's equal, which will choose to keep this item right here at index i.

(In your loop in your sortgamestate() procedure in nim.py, you will not want the 'print' statement.)

That's the first part of the inside of your loop. Secondly, we need to insert the item there, and remove it from its current location. For that, I would like to give you the following python statement which you can copy and paste into your program. But I'd like you to try to understand it, also, below.

gamestate = gamestate[0:where] + [gamestate[i]] + gamestate[where:i] + gamestate[i+1:]

This assignment statement replaces the value of 'gamestate' with a modified version, similar to the assignment statement "where = where + 1", although with a more complicated formula.

The more complicated formula is as follows. Basically we are taking apart the list and putting it back together again. Just like with strings, '+' in Python is the operator to concatenate lists. So we are taking a few chunks of the list and then putting them back together, in a slightly different order.

"gamestate[0:where]" means to take the portion of the list from index zero up to but not including the value "where". For example, if gamestate is [5,10,15,20,25], then gamestate[0:2] is [5,10].

"[gamestate[i]]" just makes a list out of gamestate[i], ready for concatenation. So for example, if gamestate[2] is 15, then [gamestate[2]] is [15].

Next, we take gamestate from 'where' up to (but not including 'i').

Finally, we take gamestate from i+1 to the end. Thus we have removed the 'i'th value here, and inserted it earlier.

For example, if gamestate was [5,10,15,20,25,30,35], i is 4, and where is 2, then we have

[5,10] + [25] + [15,20] + [30,35]