Vector.splitAt
splits a vector into two parts at the index you specify. The first part ends just before the element at the given index; the second part starts with the element at the given index. Some examples will help:
Some Examples
The most obvious use case is bisecting a vector, i.e., splitting it into two (nearly) equal parts. To do that, half the length, and use it as your splitting index:
val xs = Vector(1,2,3,4,5,6) val mid = xs.length / 2 // 3 val (left, right) = xs splitAt mid // left: Vector[Int] = Vector(1, 2, 3) // right: Vector[Int] = Vector(4, 5, 6)
But what happens if your vector contains an odd number of elements? No sweat! Because of the way integer division works, the quotient length ÷ 2 is truncated. In other words, the left
vector will always have one less element than the right
vector:
val xs = Vector(1,2,3,4,5) val mid = xs.length / 2 // 2 val (left, right) = xs splitAt mid // left: Vector[Int] = Vector(1, 2) // right: Vector[Int] = Vector(3, 4, 5)
Of course, you don’t have to cut the thing in half. You can split it anywhere:
val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 1 // left: Vector[Int] = Vector(1) // right: Vector[Int] = Vector(2, 3, 4, 5)
Or …
val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 4 // left: Vector[Int] = Vector(1, 2, 3, 4) // right: Vector[Int] = Vector(5)
What happens if you split at index 0?
val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 0 // left: Vector[Int] = Vector() // right: Vector[Int] = Vector(1, 2, 3, 4, 5)
Ah, the left
vector is empty! That’s because Vector.splitAt
starts the right
vector at the given index. There’s nothing before the given index, so the only thing left to return for left
is an empty vector.
The reverse happens if you split at the length: The right
vector is empty while the left
vector contains the entire input vector:
val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 5 // left: Vector[Int] = Vector(1, 2, 3, 4, 5) // right: Vector[Int] = Vector()
But what happens if you try to split at an index greater than the length?
val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 6 // left: Vector[Int] = Vector(1, 2, 3, 4, 5) // right: Vector[Int] = Vector()
Well, that’s interesting. So then, if you split at any index greater than the length of the input vector, the left
contains the input vector while the right
vector is empty.
You get the reverse if you split on a negative number:
val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt -1 // left: Vector[Int] = Vector() // right: Vector[Int] = Vector(1, 2, 3, 4, 5)
Merge Sort with Vector.splitAt
You can use Vector.splitAt
in performing a merge sort. Vector.splitAt
is, admittedly, a pretty small piece of the puzzle. Merge sort is a divide-and-conquer algorithm, and Vector.splitAt
just performs the divide part. Nevertheless it comes in handy for that part.
Speaking of which, start by using Vector.splitAt
to define a bisect
function that splits a vector in half:
def bisect[A](xs: Vector[A]) = { val mid = xs.length / 2 xs splitAt mid }
A merge sort breaks a vector down into single-element (or empty) vectors and then puts them back together, sorting the elements of each block as it combines them. Start with the merge
function that puts the blocks back together after you’ve broken them down:
def merge(left: Vector[Int], right: Vector[Int]) = { @tailrec def mergeWith(l: Vector[Int], r: Vector[Int], acc: Vector[Int]): Vector[Int] = { (l.isEmpty, r.isEmpty) match { // If either side is empty, just add // the non-empty side to the accumulator. case (true, _) => acc ++ r case (_, true) => acc ++ l // Compare the head elements, and add // the lesser head value to the // accumulator. Then call recursively. case _ => val lh = l.head val rh = r.head val (next, l2, r2) = if (lh < rh) (lh, l.tail, r) else (rh, l, r.tail) mergeWith(l2, r2, acc :+ next) } } mergeWith(left, right, Vector[Int]()) }
Now mergeSort
can use bisect
and merge
to break down the vector and then merge it back together:
def mergeSort(as: Vector[Int]): Vector[Int] = as match { case Vector() => as case Vector(a) => as case _ => val (l, r) = bisect(as) merge(mergeSort(l), mergeSort(r)) } val xs: = Vector(43,48,3,23,28,6,25,43,16) val sorted: Vector[Int] = mergeSort(xs) // sorted: Vector[Int] = // Vector(3, 6, 16, 23, 25, 28, 43, 43, 48)
A quick announcement: I’ve got some instructional material to develop. Unfortunately it’s going to take up a fair amount of my time. This is probably the last Scala Saturday post for a little while, but I hope to pick back up in a month or two.