Preview

02 - Insertion Sort

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

  FALSE

  TRUE

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

  a sorted portion and an unsorted portion

  the larger portion and the smaller portion

  None of the above

  x' and 'y' where x is always just 1 card or element

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

  sorted portion into the unsorted portion until the list is unsorted

  None of the above

  unsorted portion into the unsorted portion

  unsorted portion into the sorted portion until the whole list is sorted

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

  infront

  behind

  right

  left

 5. In the following list what is '23'?
23,42,4,16,8,15

  The start and end of our unsorted portion

  The start and end of our sorted portion

  None of the above

  The end point of our unsorted portion

 6. 42 is the first element in the unsorted portion and we proceed in the algorithm to …..
23,42,4,16,8,15

  None of the above

  compare the 42 to the 23 (23 being the only element in our sorted element)

  compare the 42 to the 4

  compare the 42 to the 15

 7. If 42 is larger than 23, we can…..
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)

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

  None of the above

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

 8. At this point in the insertion sort we have two elements in our unsorted list. The four is next - what happens now?
SORTED      |    UNSORTED
--------------------------------------
23   42              4    16   8    15

#What comes next?

  We do not need to move the elements in the sorted list to the right before inserting the new element.

  We have to move the 42 and the 23 right one place. and put the '4' into the first place in the sorted portion

  We simply insert the '4' before the 42, but after the 23

  We insert the '4' after the 42 and before the 16.

 9. In the following code for an insertion sort, what are the values of the variable 'index' generated by the for loop?
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)

  1 to 8

  None of the above

  0 to 9

  0 to 8

 10. In line 4, what is the first 'value' that is being assigned to the variable 'currentvalue'?
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)

  46

  1

  14

  0

 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)

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

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

  All of the above statements are correct

  position, when printed, would produce 1 to 8

 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)?
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)

  nlist[position-1] is equal to -1 which does not exist and currentvalue is equal to 1.

  nlist[position-1] is equal 1 and currentvalue is equal to 0

  nlist[position-1] is equal to nlist[1] which is 46 and currentvalue is equal to the element in index 1 which is also 46.

  nlist[position-1] is equal to nlist[0] which is 14 and currentvalue is equal to the element in index 1 which is 46.

 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

  None of the above

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

 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 adding 1 to each number, e.g. making 14, 15 and 46 is turned into 47

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

  None of the above

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

 15. Taking a look at the insertion sort algorithm again, can you fill in the blanks
Sorting is typically done in-place, by iterating up the array, 
growing the sorted list behind it. At each array-position, 
it checks the value there against the ____________ in the sorted 
list (which happens to be next to it, in the previous array-position 
checked). If _______, it leaves the element in place and moves to
 the next. If smaller, it finds the correct position within the sorted list, 
shifts all the larger values up to make a space, and inserts into that 
correct position.

  smallest value / smaller

  smallest value / largest

  largest value / smaller

  largest value / larger

 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))

  inverse case

  best case

  first case

  worst case

 17. Analyse the following example on insertion sort and fill in the blanks
The following table shows the steps for sorting the sequence
 {3, 7, 4, 9, 5, 2, 6, 1}. 

3  7  4  9  5  2  6  1
3* 7  4  9  5  2  6  1
3  7* 4  9  5  2  6  1
3  4* 7  9  5  2  6  1
3  4  7  9* 5  2  6  1
3  4  5* 7  9  2  6  1
2* 3  4  5  7  9  6  1
2  3  4  5  6* 7  9  1
1* 2  3  4  5  6  7  9

In the above example the key that was moved (or left in place 
because it was the biggest yet considered) in the previous step
is _______________________________________________

  always the '3' which is theinsertion sot key

  always the first element

  always the last element

  marked with an asterisk.

 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.

  TRUE

  FALSE

 19. This is an alternative algorithm which also performs the insertion sort. Can you fill in the blanks?
Step 1 ? If it is the first element, it is already sorted. return 1;
Step 2 ? Pick next element
Step 3 ? ___________________________________________???
Step 4 ? Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 ? Insert the value
Step 6 ? Repeat until list is sorted

  Compare with all elements in the sorted sub-list

  Shift all the element left before going to the next step

  Compare with all the elements in the unsorted sub-list

  None of the above

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

  efficiency for relatively small data sets (small lists)

  It is in-place and stable (does not change the relative order of elements)

  simple implementation

  All of the above are valid advantages