Warmup

Warmup

Part A: Sketch the Sorts

To start, we want to get an intuitive understanding of some different sorting strategies. We’ll look at selection sort, insertion sort and bubble sort. Python code for each of these algorithms is given below. To get familiar with their different approaches, we’ll practice running each of them “by hand” and illustrating their behavior with a pen and paper.

To complete this section, assume we’re sorting the following list of five integers: [4, 3, 1, 5, 2], and this list will be passed in as an argument to the parameter values (i.e., values = [4, 3, 1, 5, 2]). For each algorithm below, read through the code and follow the instructions given in the comments to illustrate the sorting algorithm’s behavior by drawing the state of the list at each step on the graph-paper template provided. Continue until the algorithm has finished, and label the resulting visualization to indicate which sorting strategy it illustrates.

Here is an example showing the first two states of Selection Sort:

Finally, after your work through each algorithm, upload photos of your completed worksheets to Codespaces and commit and sync your changes. List the names of your uploaded worksheet files in WARMUP.md.

Selection Sort

def selection_sort(values):
    for i in range(len(values) - 1):
        min_index = i
        for j in range(i+1, len(values)):
            if values[min_index] > values[j]:
                min_index = j

        values[i], values[min_index] = values[min_index], values[i]
        # PAUSE HERE: draw the current state of the list 'values' on your worksheet

Insertion Sort

def insertion_sort(values):
    for i in range(1, len(values)):
        key = values[i]
        j = i-1
        while j >= 0 and key < values[j] :
                values[j + 1] = values[j]
                j -= 1
        values[j + 1] = key
        # PAUSE HERE: draw the current state of the list 'values' on your worksheet

Bubble Sort

def bubble_sort(values):
    for end in range(len(values) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if values[i] > values[i+1]:
                swapped = True
                values[i], values[i+1] = values[i+1], values[i]
                # PAUSE HERE: draw the current state of the list 'values' on your worksheet
        if not swapped:
            return

Part B: Out of Sorts

Scan through the file test_sorts.py. You should see implementations of Selection Sort and Merge Sort (including its helper function, merge) as well as a simple function called test_sorts that runs both sorting algorithms and displays the output. Now that you’ve looked it over, run the program to verify that everything is working as expected…

Oh no, it’s actually borked. The current output is not correct. There are three lines containing errors that are causing trouble. Find them and fix them so the test demonstrates that the algorithms are working correctly. (For this part, you can ignore the lines that are commented out—we will use these in Part C.)

Part C: Comparing Runtimes

Now that your sorts are working correctly, lets do an experiment to get some intuition about how much time they take to run. Since we want to focus on the algorithms themselves (and not the speed of the hardware), we will use the number of comparisons the algorithm performs as a proxy for its runtime.

To help track the number of comparisons, uncomment the print statements in lines 5 and 15 of test_sorts.py, so each algorithm prints a . character every time it compares two items in the list.

Now inspect runtime.py. This short program provides a simple function, estimate_runtime(quantity, sort) that can generate a list of length quantity and sort it using the sorting algorithm provided as an argument.

ReadMe

You may notice that this is the first time you have used a function as an argument to another function. You do this by writing the function name without parentheses or arguments, and passing it into the estimate_runtime function as you would any other argument. The behavior is the same as with other kinds of arguments: the variable you pass in gets assigned a local alias (in this case, sort) that can be used inside the estimate_runtime function. Other than the name, nothing else changes, and sort can be called in the usual way—i.e., sort(items)

By default, running this program at the command-line will generate a list of 8 items, sort them using both selection sort and merge sort, and print a period everytime it compares two items. Try running it to see what this looks like.