I recommend making a folder for today’s lab in COURSES as you usually do.

There is room on your class worksheet to write down answers to the following exercises.

Exercise 1

Here is the code for insertion sort from the reading:

Discuss the following questions about the program itself:

  • Why doesn’t this function require a return value?
  • Why are we using a while loop for cur_pos rather than a for loop?
  • Why doesn’t i start at 0?

Exercise 2

a) Come up with two lists of length 5 with the following properties:

  • One for which insertion sort will go as fast as possible
  • One for which insertion sort will go as slow as possible

b) How many times does insertion sort need to shift values when performed on each of the two lists you created?

Exercise 3

a) Using big-O analysis, determine what is the best case runtime of insertion sort.

b) Using big-O analysis, determine what is the worst case runtime of insertion sort.

Exercise 4

Here is another version of selection sort:

def selection_sort(lst):
  for i in range(len(lst)):
    small = i
    for j in range(i+1, len(lst)):
      if lst[j] < lst[small]:
        small = j
    if small != i:
      lst[i], lst[small] = lst[small], lst[i]

a) Using big-O analysis, determine what is the best case runtime of selection sort.

b) Using big-O analysis, determine what is the worst case runtime of selection sort.

c) Given these best- and worst-case runtimes, do you think insertion sort is better or worse than selection sort? (The code for selection sort is below.)

Submission

Submit your answers for Exercises 3 and 4 to Moodle for an extra engagement credit.

Extra 1

Adapt the code from function_timer.py and the reading to perform benchmark tests on each of the sorting algorithms in the best and worst case to see how they do.

Extra 2

If you have extra time, try coming up with a sorting algorithm that has a similar ‘divide and conquer’ approach as binary search (i.e. makes two recursive calls to split the list into two halves).