Implementing insertion sort

In this step, you are going to implement insertion sort in Python.

To start with — just like bubble sort — you need a short list to test your algorithm on.

my_list = [5,9,5,8,1,3]

You should write the algorithm as a function, again with a single parameter (the list to be sorted). Make sure to comment your code to explain what each part is accomplishing.

def insertion_sort(list_to_sort):

Requirements

Your function needs to do the following:

1. Create a for loop that will iterate over the list that you receive as a parameter, making sure the loop starts at the second item (index 1).

2. Each time the loop runs, you first need to pull the item to be inserted out of the list. You can access it using the index from the for loop. I will call this the key.

3. In order to insert the item into the sorted sublist, you will need another index variable that starts at the last index in the sorted sublist and is always the item before the current item you are trying to insert. You can get this by taking one away from the for loop variable. I will call this the marker from now on.

4. Create a while loop with two conditions, it will keep running while:

   • The current item in the sorted sublist (indicated by the marker) is greater than the key

   • AND

   • The marker is greater than or equal to 0

5. Inside the loop:

   • Move the item at the marker’s position up one place in the list

   • Take one away from the marker variable

6. When the loop finishes, you should add the item to be inserted at the position indicated by the marker.

Code snippets

Here are a few code snippets to help you implement this algorithm, you will have to change these to suit your program:

• Creating a for loop that starts at the second item of a list.

for item in range(1, len(list_to_sort))

The variable item will start with a value of 1 rather than 0.

• Grab the item in a list using the for loop variable.

key = list_to_sort[item]

• Using a while loop with two conditions.

while item > 0 and item < 10:

Make sure that both sides of the and are full condition statements. A common mistake is to write a loop like this: while item > 0 and < 10 but this will cause a syntax error.

• Moving an item one spot to the right in a list.

list_to_sort[marker + 1] = list_to_sort[marker]

This does not swap the items, rather it just copies the value from the marker’s position to the next one along in the list. It is important that you have the current item stored in a variable so it can be replaced when you find the right spot.

Have a go at generating the algorithm. If you get stuck, ask for help in the comments below. If you get totally lost, then you can have a peek at a solution on Rosetta Code. These examples have not used relevant names for their variables, be sure that your function uses variable names that relate to the data stored in that variable.