Preparation

Download the sorting_lab.py starter file and open it in Brackets. Also open a Terminal in the same directory in order to easily run the code.

Exercise 1

a. Read the documentation and code for smallest_index to make sure you understand what it is doing.

b. Predict what smallest_index will return if executed on the following arguments:

>>> smallest_index(["a", "c", "k", "b", "d"], 0)
>>> smallest_index(["a", "c", "k", "b", "d"], 1)
>>> smallest_index(["a", "c", "k", "b", "d"], 3)
>>> smallest_index(["a", "c", "k", "b", "d"], 4)

c. Verify your predictions in the REPL. Remember that you can import the functions using

>>> from sorting_lab import *

Exercise 2

a. Read the documentation and code for selection_sort to make sure you understand what it is doing.

b. Try running selection_sort on a variety of lists such as the following.

>>> lst = ["a", "c", "k", "b", "d"]
>>> selection_sort(lst)
>>> print(lst)

c. Let’s print off intermediate values of the list as selection_sort is running. Add the following line of code at the top of the for loop of selection_sort just before the smallest_index function is called.

print(lst[:i], lst[i:])

d. Close the REPL, reopen it, and re-import the functions from sorting_lab.

e. Execute selection_sort on the following lists and pay careful attention to how the list changes during the execution of the function.

>>> selection_sort(["a", "c", "k", "b", "d"])
>>> selection_sort([900, 800, 700, 600, 500, 400, 300, 200, 100])
>>> selection_sort([100, 200, 300, 400, 500, 600, 700, 800, 900])
>>> selection_sort([100, 100, 100, 100, 100])

Exercise 3

a. Review the documentation and code for merge to make sure you understand what it is doing.

b. Predict what the values of lst1, lst2, and lst3 will be after merge is executed.

>>> lst1, lst2, lst3 = [10, 40, 70], [20, 30, 50], [None]*6
>>> merge(lst1, lst2, lst3)

c. Verify your prediction in the REPL.

d. What do you think will happen if lst1 and lst2 are not sorted properly? Test this in the REPL.

e. Uncomment the calls to print inside the merge function. Then try calling merge on the following inputs and pay careful attention to how the lists change during the execution of the function.

>>> merge([20, 40, 60], [10, 30, 50], [None]*6)
>>> merge([10, 70], [20, 30, 40, 50], [None]*6)
>>> merge([90], [70, 80, 90, 100, 110], [None]*6)
>>> merge([10, 10, 10], [10, 10, 10], [None]*6)

f. Re-comment the print lines inside the merge function before going on to exercise 4.

Exercise 4

a. Read the documentation and code for merge_sort to make sure you understand what it is doing.

b. Try running merge_sort on a variety of lists such as the following.

>>> lst = [10, 30, 90, 20, 40]
>>> merge_sort(lst)
>>> print(lst)

c. Let’s watch the order in which recursive calls happen. Add the following line of code at the top of the merge_sort function just before the if statement.

print(lst)

d. Close the REPL, reopen it, and re-import the functions from sorting_lab.

e. Execute merge_sort on the following lists and pay careful attention to the order in which the recursive calls are made.

>>> merge_sort([10, 30, 90, 20, 40])
>>> merge_sort([90, 80, 70, 60, 50, 40, 30, 20, 10])
>>> merge_sort([10, 20, 30, 40, 50, 60, 70, 80, 90])
>>> merge_sort([10, 10, 10, 10, 10])

Exercise 5

a. Delete all of your print statements in both selection_sort and merge_sort. Then close and reopen the REPL.

b. Import the sorting lab again along with the shuffle function from the random library.

>>> from sorting_lab import *
>>> from random import shuffle

c. Let’s compare the speeds of the two sorting algorithms. Create two identical lists with randomly organized numbers.

>>> lst1 = list(range(10000))
>>> shuffle(lst1)
>>> lst2 = lst1.copy()

d. Now sort them.

>>> selection_sort(lst1)
>>> merge_sort(lst2)

e. Now try increasing the sizes of the lists and sorting them again making note in how the times change.

Exercise 6

Suppose that we have the following class.

class Person:
    """A person object has a first name, last name, and age."""

    def __init__(self, first, last, age):
        """Constructs a new person with a first name, last name, and age."""
        self.first = first
        self.last = last
        self.age = age

    def firstName(self):
        """Returns the first name of the person"""
        return self.first

    def lastName(self):
        """Returns the last name of the person"""
        return self.last

    def age(self):
        """Returns the age of the person"""
        return self.age

    def __str__(self):
        """Turns the object into a human-readable string"""
        return self.first + "," + self.last + "," + str(self.age)

Recall that the built-in sort method for lists allows us to sort by a key. For example, if we have a list of Person objects, we can sort them in a variety of ways:

>>> p1 = Person("Lois", "Lane", 34)
>>> p2 = Person("Clark", "Kent", 36)
>>> p3 = Person("Lex", "Luthor", 59)
>>> lst = [p1, p2, p3]
>>> lst.sort(key = Person.firstName)
>>> for p in lst: print(p)
>>> lst.sort(key = Person.lastName)
>>> for p in lst: print(p)
>>> lst.sort(key = Person.age)
>>> for p in lst: print(p)

a. Copy the Person class into your lab file.

b. Copy the following main code into your lab file.

def main():
    p1 = Person("Lois", "Lane", 34)
    p2 = Person("Clark", "Kent", 36)
    p3 = Person("Lex", "Luthor", 59)
    lst = [p1, p2, p3]

    # selection_sort(lst, Person.firstName)
    # selection_sort(lst, Person.lastName)
    # selection_sort(lst, Person.age)

    for p in lst:
        print(p)

if __name__ == "__main__":
    main()

c. Modify the selection_sort function to take in an additional parameter called key that is a function or method and uses it to determine what component to sort the list by.

d. Try sorting the list of people using selection_sort with an arbitrary key by commenting out the appropriate calls in the main code and running

$ python3 sorting_lab.py

e. If you still have time, modify merge_sort to also take in a function key as a parameter that allows it to sort by any component of an object.

Exercise 7

If you still have time, consider exploring the insertion_sort function and insert_left function in the sorting_lab.py file. Try running them on various inputs and comparing their runtime to selection sort and merge sort for larger lists.