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:

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
...