Testing MergeSort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import scala.reflect.ClassTag | |
import org.scalacheck._ | |
case class Histogram[K] private (value: Map[K, Int]) { | |
def +(key: K): Histogram[K] = { | |
val count = value.getOrElse(key, 0) + 1 | |
Histogram(value + (key -> count)) | |
} | |
} | |
object Histogram { | |
def empty[K]: Histogram[K] = new Histogram(Map.empty) | |
def apply[K](keys: Seq[K]): Histogram[K] = | |
keys.foldLeft(Histogram.empty[K])(_ + _) | |
} | |
object Sorting { | |
def mergeSort[T: ClassTag](a: Array[T])(implicit o: Ordering[T]): Unit = { | |
val aux = new Array[T](a.length) // Use a common auxiliary array | |
// Sort the subsequence [l, h] | |
def sort(l: Int, h: Int): Unit = { | |
if (l < h) { | |
val m = l + (h - l) / 2 // Account for integer overflow | |
sort(l, m) | |
sort(m + 1, h) | |
if (o.gt(a(m), a(m + 1))) { | |
merge(l, m, h) // Only merge if [l, h] is not in order | |
} | |
} | |
} | |
// Merge the sorted subsequences [l, m] and (m, h] | |
def merge(l: Int, m: Int, h: Int): Unit = { | |
for (i <- l until h + 1) { | |
aux(i) = a(i) | |
} | |
var i = l | |
var j = m + 1 | |
for (k <- l until h + 1) { | |
if (i > m) { | |
a(k) = aux(j) | |
j += 1 | |
} else if (j > h) { | |
a(k) = aux(i) | |
i += 1 | |
} else if (o.lt(aux(j), aux(i))) { | |
a(k) = aux(j) | |
j += 1 | |
} else { | |
a(k) = aux(i) | |
i += 1 | |
} // n.b. Stable implementation of the algorithm | |
} | |
} | |
sort(0, a.length - 1) // Run the routine on the whole array | |
} | |
def isSorted[T](a: Array[T])(implicit o: Ordering[T]): Boolean = | |
Range(0, a.length - 1).forall(i => o.lteq(a(i), a(i + 1))) | |
} | |
object SortingSpecification extends Properties("mergeSort") { | |
import Sorting._ | |
val array: Gen[Array[Int]] = | |
Gen.containerOf[Array, Int](Gen.posNum[Int]) | |
property("isSorted") = Prop.forAll(array) { a => | |
mergeSort(a) | |
isSorted(a) | |
} | |
property("hasSameKeys") = Prop.forAll(array) { a => | |
val before = Histogram(a.toList) | |
mergeSort(a) | |
val after = Histogram(a.toList) | |
before == after | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment