Point Pelewin: 2010-01

(Part 1 2 3)

Odds and Ends

In the first two parts, I demonstrated visualization of the process of merge sorting an array of integers. In this part I will describe the two steps left undescribed: how to create a collection of stages and how to create a repeating iterator. I will also present a shuffling function that can be used to create the initial state.

The Stages class

The Stages class provides a map method which is used by the SortStates class to create a collection of states. The function that creates one of the states needs to 1) see the state array (which contains the previous state) and 2) be told how to rearrange it into the next state. The actual function passed to map is curried with the state array, so the only thing map needs to prepare is the collection of stages of rearrangement information.

class Stages (n: Int) {
   Define generate method 

  def map (f: List[Int] => Array[Int]) =
    generate() map f
}

Define generate method

The generate method creates the stages recursively, bottoming out when the parameter i exceeds n.

  private def generate (i: Int = 2): List[List[Int]] = {
     Define split subroutine 

    if (n <= i) {
       Base case 
    } else {
       Preceding cases 
    }
  }

Base case

In the base case, the state array (whose length is stored in the n field) is in a partially sorted state where two sublists of roughly equal length are individually sorted (e.g. Array(1, 3, 5, 0, 2, 4)) and are to be merged into a completely sorted array. The conversion function, of class StateFunc (described in part 2), will be able perform this operation if given a list containing the total length of the sublists, i.e. List(n).

      List(n) :: Nil

Preceding cases

In each of the cases preceding the base case, the state array consists of k pairs of sorted sublists that are to be merged into k sorted sublists (which will be merged in the next stage, and so on). Thus, in the general case C_x the stage information is a list of 2 × k integers where the sum of each pair is equal to the corresponding integer in the stage information of the following case C_x+1.

      val tail = generate(2 * i)
      split(tail.head) :: tail

Define split subroutine

The split subroutine uses h to create a list of integers whose size is twice that of h and where every element e ∈ h is mapped to two elements, the first being e/2 and the second being e-e/2.

    def split (h: List[Int]) =
      h flatMap { e => List(e/2, e-e/2) }

The RepeatingIterator class

The RepeatingIterator class trivially encapsulates a sequence and overrides the next method to reset the internal iterator every time it is exhausted. The hasNext method accordingly always returns true.

class RepeatingIterator[A] (xs: Seq[A]) extends Iterator[A] {
  private var iter = xs.iterator
  override def hasNext = true
  override def next () = {
    if (!iter.hasNext) iter = xs.iterator
    iter.next
  }
}

Shuffling the values

In the example, I passed an array of values in reverse order to SortStates. Alternatively, the array can be shuffled like this:

object Shuffle {
  private val rand = new scala.util.Random

  def apply[A] (xs: Array[A]) = {
    for (n <- 0 until xs.size) {
      val k = n + rand.nextInt(xs.size-n)
      val v = xs(k)
      xs(k) = xs(n)
      xs(n) = v
    }
    xs take xs.size
  }
}

And that's merge sort.

Point Pelewin

2010-01-27

The Literate Programming Wiki

2010-01-12

Unsung

Established 1993

2010-01-02

Merge sort in Scala and Processing (3/3)