1. Insertion sort is a simple sorting algorithm that works the way most people sort playing cards in their hands

2. The basic idea behind insertion sort is to divide our list into two portions:

3. At each step of the algorithm an element is moved from the ..

4. Typically, the sorted numbers go to the _____of the unsorted numbers.

5. In the following list what is '23'?

6. 42 is the first element in the unsorted portion and we proceed in the algorithm to …..

7. If 42 is larger than 23, we can…..

append 42 to the end of the 'sorted' list. (e.g. 23, 42 / 4,16,8,15

remove 42 and take it to the end of the list as it is largest (e.g. 23,4,16,8,15,42)

include 42 before the 23 (e.g. 42,23 / etc)

None of the above

8. At this point in the insertion sort we have two elements in our unsorted list. The four is next - what happens now?

9. In the following code for an insertion sort, what are the values of the variable 'index' generated by the for loop?

10. In line 4, what is the first 'value' that is being assigned to the variable 'currentvalue'?

11. On line 5, what is the variable 'position'?

def insertionSort(nlist):
for index in range(1,len(nlist)):
currentvalue = nlist[index]
position = index
while position>0 and nlist[position-1]>currentvalue:
nlist[position]=nlist[position-1]
position = position-1
nlist[position]=currentvalue
nlist = [14,46,43,27,57,41,45,21,70]
insertionSort(nlist)
print(nlist)

position is being assigned the value of the 'index number'

The position variable, if printed, would the same as 'index'

position, when printed, would produce 1 to 8

All of the above statements are correct

12. On line 7 the while loop needs to find out what the values of 'nlist[position-1)' and 'currentvalue' are. What are they (in the first iteration of the for loop)?

13. In the first iteration on line 7, is the while loop condition (while position>0 and nlist[position-1]>currentvalue:) TRUE or FALSE?

def insertionSort(nlist):
for index in range(1,len(nlist)):
currentvalue = nlist[index]
position = index
while position>0 and nlist[position-1]>currentvalue:
nlist[position]=nlist[position-1]
position = position-1
nlist[position]=currentvalue
nlist = [14,46,43,27,57,41,45,21,70]
insertionSort(nlist)
print(nlist)

The position is greater than 0, but 14 is NOT greater than 46, so the loop does not run and line 11 is executed instead

The position is not greater than 0 so the loop does not run

The position is greater than 0 and 46 is greater than 14, so the loop runs (14 is printed)

None of the above

14. What is line 9 doing?

def insertionSort(nlist):
for index in range(1,len(nlist)):
currentvalue = nlist[index]
position = index
while position>0 and nlist[position-1]>currentvalue:
nlist[position]=nlist[position-1]
position = position-1
nlist[position]=currentvalue
nlist = [14,46,43,27,57,41,45,21,70]
insertionSort(nlist)
print(nlist)

It is decrementing the value of 'position' so that the list is searched from end to beginning

It is adding 1 to each number, e.g. making 14, 15 and 46 is turned into 47

None of the above

It is incrementing the value of 'position' so that it goes through the list

15. Taking a look at the insertion sort algorithm again, can you fill in the blanks

16. In an insertion sort, the ______________input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n))

17. Analyse the following example on insertion sort and fill in the blanks

18. The insertion sort is suitable for large data sets as its average and worst case complexity are of ?(n2), where n is the number of items.

19. This is an alternative algorithm which also performs the insertion sort. Can you fill in the blanks?

20. The advantages of an insertion sort include the following: