Programming project 7

QuickSelect

Consider the following function select(A: List[String], k: Int): String:

def select(A: List[String], k: Int): String = { 
  val B = A.sorted
  B(k)
}

This function returns the \(k\)th smallest value in the list. For instance, if k = 0, it returns the smallest element, when k = A.length - 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 quickSelect(A: List[String], k: Int): String that returns the same result as select, but which does not sort the list. Your code should be faster than sorting on average.

Hint: Use the idea of Quicksort. Pick a pivot, and partition the list into pieces based on the pivot. Then recursively look for an element in one of the pieces.

Write test code that measures the running time of select and quickSelect for a large, unsorted list, and prints out timing information. Which function is faster?

Mergesort without recursion

Mergesort can be implemented without recursion by using a queue of queues. You start by creating an empty queue \(Q\). For each element \(x\) of the input list \(L\), make a queue with one element and enqueue it in \(Q\). Then, as long as \(Q\) contains more than one element, dequeue the first two elements, merge them, and enqueue the result. Finally return the contents of the single element remaining in \(Q\).

Submit a Scala file queuesort.scala containing a function with the following argument and result type:

  def mergeSort(data: List[Int]): List[Int] = {
    // fill in
  }

The function should implement the strategy above for sorting the input list. Use the Scala library Queue.

Inside the source file, explain (in a comment) why this algorithm correctly sorts the list, and analyse its running time. What is the loop invariant?

Mergesort for doubly-linked list

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

Download doublylinkedlist.scala and implement the following methods:

median: Node[T] This method returns the node in the middle of the list:
```
scala> a
res3: DoublyLinkedList[Int] = [1,2,3]
scala> a.median.el
res5: Int = 2
scala> a.append(4)
scala> a.median.el
res7: Int = 2
scala> a.append(5)
scala> a.median.el
res9: Int = 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: Node[T]): DoublyLinkedList[T] 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's okay for n to be the front sentinel of this list, but of course not the rear sentinel.

Here are some examples:

scala> a
res8: DoublyLinkedList[String] = [CS206,is,fun,and,one,learns,a,lot]
scala> val n = a.first.next.next
n: Node[String] = Node@4a9a6cc8
scala> n.el
res9: String = fun
scala> val b = a.split(n)
b: DoublyLinkedList[String] = [and,one,learns,a,lot]
scala> a
res10: DoublyLinkedList[String] = [CS206,is,fun]
scala> a.split(a.last)
res11: DoublyLinkedList[String] = []
scala> a
res12: DoublyLinkedList[String] = [CS206,is,fun]
scala> val c = b.split(b.first)
c: DoublyLinkedList[String] = [one,learns,a,lot]
scala> b
res13: DoublyLinkedList[String] = [and]
scala> val d = a.split(a.first.previous) // split on front sentinel
d: DoublyLinkedList[String] = [CS206,is,fun]
scala> a
res14: DoublyLinkedList[String] = []

steal(other: DoublyLinkedList[T]) 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:

scala> a
res10: DoublyLinkedList[Int] = [1,3,13,17,27]
scala> b
res11: DoublyLinkedList[Int] = [2,15,16,25]
scala> a.steal(b)
scala> a
res13: DoublyLinkedList[Int] = [1,3,13,17,27,2]
scala> b
res14: DoublyLinkedList[Int] = [15,16,25]
scala> a.steal(b)
scala> a
res16: DoublyLinkedList[Int] = [1,3,13,17,27,2,15]
scala> b
res17: DoublyLinkedList[Int] = [16,25]
scala> b.steal(a)
scala> b
res19: DoublyLinkedList[Int] = [16,25,1]
scala> a
res20: DoublyLinkedList[Int] = [3,13,17,27,2,15]

merge(other: DoublyLinkedList[T]) 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:
```
scala> a
res30: DoublyLinkedList[Int] = [3,13,17,27]
scala> b
res31: DoublyLinkedList[Int] = [2,15,16,25]
scala> a.merge(b)
scala> a
res33: DoublyLinkedList[Int] = [2,3,13,15,16,17,25,27]
scala> b
res34: DoublyLinkedList[Int] = []
```

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

  def sort() {
    // is length <= 1 ?
    if (isEmpty || front.next.next == rear)
      return
    val other = split(median)
    sort()
    other.sort()
    merge(other)
  }

Note how it determines in constant time if the length of the list is at most one—calling length instead would have taken linear time.

I have made a test suite checklistsort.scala to test the four methods. As usual, you run it as

$ fsc doublylinkedlist.scala 
$ fsc checklistsort.scala 
$ scala org.scalatest.run CheckListSortSuite
Run starting. Expected test count is: 5
...