Preparation

Download the sorting_lab.py starter file and open it up in Brackets and open a Terminal in the same directory as the file.

Exercise 1

In this exercise, we are going to lay the ground work to analyze the runtime of selection_sort. We are going to count the number of times certain statements are reached in the code so that we can measure approximately how many steps are required to sort the list.

a. Add the following variable as a global variable above the selection_sort definition. This variable will keep track of our count as selection sort runs.

ss_count = 0

b. Inside the selection_sort function, add the following line of code immediately before the for loop declaration. This line of code causes the ss_count variable in this function to be the global one defined earlier.

global ss_count

c. Now add the following line of code inside the for loop. This will increment the count every time the for loop is executed.

ss_count = ss_count + 1

d. We still need to count the steps in the smallest_index function, so let’s do the same thing. Add the global ss_count line to the beginning of the smallest_index function just before the smallest = start line.

e. Finally, add the line ss_count = ss_count + 1 inside the for loop so that it is incremented every time the loop executes.

Exercise 2

In this exercise, we will write a function that uses our ss_count variable to do experiments on various sized lists. One thing that will be handy is generating random lists of various sizes.

a. Open up a REPL and type the following code:

>>> import random
>>> random.sample(range(10), 7)

b. Try changing the 10 and the 7 to other numbers to see what the result is.

The sample(sequence, k) function allows us to generate a list of numbers by randomly sampling k of them from sequence. We can use this to generate random large lists to test our function on.

c. Now add the following line to the top of your lab file:

import random

d. Copy the following function into your lab file:

def ss_experiment(n):
    global ss_count
    ss_count = 0
    lst = random.sample(range(n), n)
    selection_sort(lst)
    print("steps:", ss_count)

The function, when given an input n, will count the number of steps it takes selection_sort to sort a random list of length n.

e. In your REPL, import your lab file for today and execute ss_experiment on various values of n such as 1000, 2000, 4000, 8000, and 16000.

f. Is the ss_count growing in a quadratic way like we predicted? Discuss with your partner.

Exercise 3

Now let’s measure the runtime of merge_sort and compare it to our selection sort analysis.

a. Add the following variable near the top of the lab file:

ms_count = 0

b. Inside the merge_sort function, add the following two lines of code at the very top of the function above the if statement.

global ms_count
ms_count = ms_count + 1

c. Now we need to count the steps in the merge function, so let’s do the same thing. Add the global ms_count line to the beginning of the merge function just before the i = len(out) line.

d. Next, add the line ms_count = ms_count + 1 inside all of the for loops so that it is incremented every time any one of the loop executes.

e. Now copy the following function into your lab file:

def ms_experiment(n):
    global ms_count
    ms_count = 0
    lst = random.sample(range(n), n)
    merge_sort(lst)
    print("steps:", ms_count)

f. Now close and reopen your REPL, import your lab file for today and execute ms_experiment on various values of n such as 1000, 2000, 4000, 8000, and 16000.

g. Is the ms_count growing in an n*log(n) way like we predicted? Discuss with your partner.

Exercise 4

If you have extra time, use the same methods to experiment with the running times of linear search and binary search. You can find the code for them here: searching functions.

Exercise 5

If you still have extra time, continue working on your final project.