Programming project 8

Download the archive pp8.zip. 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 timing.py to measure the run time of both select and quick_select.

You can use the unit tests test_quickselect.py to check your implementation.

Submission: Upload your file selection.py 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 listsort.py:

• median(): This method returns the node in the middle of the list:

  >>> a = DoublyLinkedList(1, 2, 3)
  >>> a.median()
  <2>
  >>> a.append(4)
  >>> a
  [1, 2, 3, 4]
  >>> a.median()
  <2>
  >>> a.append(5)
  >>> a
  [1, 2, 3, 4, 5]
  >>> a.median()
  <3>
  

  Note that when the length of the list is odd, the median is the one exactly in the middle. When the length of the list is even, it's the last element of the left half.

  You must not compute the length of the list—that is less efficient. Start by walking from the front and the rear of the list at the same time until the two references meet in the middle.

• split(n): This method splits the list after the node n. The front part of the list until (and including) node n remains in this list object, the remainder is returned as a new DoublyLinkedList object.

  The method must run in \(O(1)\) time. It should not create any new nodes (except for the sentinels of the new list)—all the original list nodes should be used.

  It is allowed for n to be the front sentinel of this list: in that case this list becomes empty, all list elements become part of the returned object. It is not allowed for n to be the rear sentinel.

  Here are some examples:

  >>> a = DoublyLinkedList("CS206","is","fun","and","one","learns","a","lot")
  >>> n = a.first().next.next
  >>> n
  <'fun'>
  >>> b = a.split(n)
  >>> a
  [CS206, is, fun]
  >>> b
  [and, one, learns, a, lot]
  >>> c = b.split(b.first())
  >>> b
  [and]
  >>> c
  [one, learns, a, lot]
  >>> d = a.split(a.first().prev) # split on front sentinel
  >>> a
  []
  >>> d
  [CS206, is, fun]
  

• steal(other): This method takes the first node of the other list, removes it from the other list, and appends it to this list.

  This method must run in constant time, and does not create any new nodes (it "steals" the node from the other list and uses it for this list).

  For example:

  >>> a = DoublyLinkedList(1,3,13,17,27)
  >>> b = DoublyLinkedList(2,15,16,25)
  >>> a
  [1, 3, 13, 17, 27]
  >>> b
  [2, 15, 16, 25]
  >>> a.steal(b)
  >>> a
  [1, 3, 13, 17, 27, 2]
  >>> b
  [15, 16, 25]
  >>> b.steal(a)
  >>> a
  [3, 13, 17, 27, 2]
  >>> b
  [15, 16, 25, 1]
  

• merge(other): This method assumes that this list is sorted in non-decreasing order, and that the other list is also sorted in non-decreasing order. It merges the nodes of both lists into this list, "stealing" them from the other list (so at the end the other list is empty).

  This method must run in \(O(n + m)\) time, where \(n\) is the size of this list and \(m\) is the size of the other list. It must not create new nodes, and instead use the nodes of the other list.

  For example:

  >>> a = DoublyLinkedList(1,3,13,17,27)
  >>> b = DoublyLinkedList(2,15,16,25)
  >>> a
  [1, 3, 13, 17, 27]
  >>> b
  [2, 15, 16, 25]
  >>> a.merge(b)
  >>> a
  [1, 2, 3, 13, 15, 16, 17, 25, 27]
  >>> b
  []
  

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._front.next.next == self._rear:
      return
    other = self.split(self.median())
    self.sort()
    other.sort()
    self.merge(other)

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 test_listsort.py to test the four methods.

Submission: Upload your file listsort.py to the submission server.