An insertion sort program in Python
We saw in the previous work how an insertion sort actually works. The insertion sort algorithm we had didn't really 'roll off the tongue' so we are going to tidy it up and write it in pseudo-code:
Get an array called myArray
for j = all of the elements in myArray, starting with the second element
key = myArray[j] # key is the data at position j.
i = j - 1 # i is the first position of the element just before j
while <not first position in array> and <myArray[i] > key> #Swap elements if you need to!
myArray[i+1] = myArray[i] # swap the big value with the small value.
i = i-1 # now get ready to check the element down the list.
myArray[i+1] = # make sure you keep track of the key you are using!
What we are doing is exactly what we described in the previous lesson. We are starting with the data at the second element position (at position 1, not 2, remember) and comparing it to the data at the first element position. If the data in the first position is bigger than the data in the second position, we have to swap them. Then we look at the data in the third position. We do exactly the same as above, comparing position 3 with 2, and then if necessary, position 2 with 1.
Q1. Writing code from an algorithm takes some practice. Type this in using Python and get it working. Test it thoroughly and check it carefully. Just because code runs and gives you some results doesn't mean the results are correct!