Homework 11:
searching and sorting
Note the due date for this assignment.
Part 1: search trees
For the first two problems below, you are to enhance a class definition of a binary search tree. We’ve provided starting source code for you to download. It contains the definition of a BSTNode class that describes the nodes that make up the structure of a binary search tree. Each such node n has an n.key and an n.value, the two components that serve as an item for a dictionary data structure. It also has two references n.left and n.right that may link to other nodes in the tree or, like a linked list, might have the value None.
The file also contains a definition of a BSTree class that is a binary search tree implementation of an ordered dictionary as described in lecture. A binary search tree object t has a single attribute t.root that refers to the root node of the tree, an object of type BSTnode. Included in that class are definitions of methods for inserting and updating entries in the dictionary (set_value), looking up dictionary items’ values by their key (get_value), computing the number of entries in the dictionary (size), finding the minimum-valued key (min_key), and gathering all the entries into a list (as_list). These should be familiar to you as you saw similar code in lecture.
Below we ask you add four methods to the BSTree class. In all our examples illustrating how they are to work, you can assume we’ve typed the following into Python:
>>> t1 = BSTree()
>>> t1
{}
>>> t2 = BSTree()
>>> t2.set_value("carlos", 17)
>>> t2.set_value("anna", 31)
>>> t2.set_value("ben", 90)
>>> t2.set_value("abe", 5)
>>> t2.set_value("angel", 14)
>>> t2.set_value("davide", 89)
>>> t2
{'abe': 5, 'angel': 14, 'anna': 31, 'ben': 90, 'carlos': 17, 'davide': 89}
Part 2: sorting
The last two problems ask you to write two classic sorting algorithms, selection sort and count sort. The autograder for each will determine whether the code you submit sorts, but it can’t check whether you’ve used the requested sorting strategy. We will go through and verify that your code is correctly written to our specification to determine your final grade for these two problems.
You can inspect our lecture code for sorting at this link.
[HW11 P1]
Exercise: search path
Write a method def search_path(self, k) that takes a key k of an entry that may or may not be in the dictionary. Like get_value, it should search through the tree looking for that key. It should return a list of strings describing the path taken from the root node to search for that key, a series of "L" and "R". If the key is in the tree, then the list returned describes where in the tree that key’s node sits. If the key is not in the tree, then the list returned describes where in the tree that key’s node would be placed were it to be inserted into the tree.
>>> d = t2.search_path("davide")
>>> d
['R']
>>> b = t2.search_path("ben")
>>> b
['L', 'R']
>>> t2.search_path("bao")
['L', 'R', 'L']
>>> t2.search_path("carlos")
[]
>>> t1.search_path("jim")
[]
[HW11 P2]
Exercise: apply
Write a method def apply(self, f) that takes a function on the values that are stored in the nodes of the binary search tree. It should modify the value of each node n to instead store f(n.value).
>>> t2.apply(lambda x: x+10)
>>> t2
{'abe': 15, 'angel': 24, 'anna': 41, 'ben': 100, 'carlos': 27, 'davide': 99}
You might want to look at the size method to see how it works. It uses a recursive helper method that performs the work of touching every node in the tree.
[HW11 P3]
Exercise: selection sort
Selection sort is a method for sorting a list that works by placing the 0-th item, then the 1st item, then the 2nd item, and so on until the list is sorted. It works in place, meaning that it swaps values around (like bubble sort) until the list is sorted. It works by making n-1 passes for a list of length n. Let’s number these passes from 0 to n-2.
For the 0-th pass, we scan through the whole list to find the minimum element in the list. We then swap that element with the element at position 0. For the 1st pass, we scan through elements 1 through n-1 to find the minimum of those elements. We then swap that element with the element at position 1. We continue in this way. In the i-th pass, we scan through elements i through n-1 to find the next minimum value, then perform a swap to place it at position i.
Once we complete the pass numbered n-2, the whole list will be sorted.
Write a function def selectionSort(someList) that sorts someList it is given using selection sort. Note that your code should not return a sorted list. Instead, it should rearrange the items that are stored in the list it is given.
[HW11 P4]
Exercise: count sort
There are situations in coding where the list of integers that we need to sort are drawn from a limited range. For example, the list
[1, 2, 0, 0, 1, 3, 2, 1, 0, 1, 3, 3, 3, 1, 0, 1, 0]
only has elements with values between 0 and 3. When that is the case, it is common to use a special sort called count sort.
Here is how it works. Assume that the numbers in our list are integers from 0 up to m-1. There are two phases. In the first phase we scan through the list and count the number of occurrences of each integer in that list. This is done by making a list of counts count, of length m, where count[i] is the number of times that the value i occurs in the list we are sorting. It makes one pass through the list in order to figure out all these counts.
For the list above, the count list is of length 4 and has the contents
[5, 6, 2, 4]
because 0 appears five times, 1 appears six times, 2 appears twice, and 3 appears four times.
In the second phase, we “rewrite” the list we are sorting to have that data in order. That is, we do the work to place the m values in order into the list according to their counts. For the example list, that ultimately places five 0s, six 1s, two 2s, and four 3s to obtain the list contents
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3]
Write a function def countSort(someList, m) that is given a list and the value of m (indicating that the list values are from 0 to m-1) and sorts the contents of someList using count sort. Note that your code should not return a sorted list. Instead, it should modify the list it is given so that the data is in sorted order.