Programming project 8

Download the archive It contains all the files for this project.

Part 1: QuickSelect

Consider the following function select(a, k):

def select(a, k):
  b = sorted(a)
  return b[k]
This function returns the \(k\)th smallest value in the list a. For instance, if k = 0, it returns the smallest element, when k = len(a) - 1, it returns the largest element.

Note that even if the input list a is not sorted, the function still selects the \(k\)th element correctly.

Your task is to write a function quick_select(a, k) that returns the same result as select(a, k), but which does not sort the list. Your code will be faster than sorting on average.

Follow the strategy of Quicksort (the quick_sort function is available in a separate file for your reference). Pick a pivot, and partition the list a into pieces based on the pivot. Look at the length of each piece, and determine where to look for the \(k\)th element recursively. Different from Quicksort, you go into recursion in one piece only.

Use the script to measure the run time of both select and quick_select.

You can use the unit tests to check your implementation.

Submission: Upload your file to the submission server.

Part 2: Merge Sort for linked List

In this project, we implement merge sort for a doubly-linked list.

Your task is to add several methods to the DoublyLinkedList class provided in

When you are done with these three methods, the sort method that is already implemented will work correctly:

  def sort(self):
    # is length <= 1 ?
    if self.is_empty() or == self._rear:
    other = self.split(self.median())
Note how it determines in constant time if the length of the list is at most one—using len(self) instead would have taken linear time.

You can use the unit tests to test the four methods.

Submission: Upload your file to the submission server.