Skip to content

Instantly share code, notes, and snippets.

@bfdes
Last active October 26, 2021 22:35
Embed
What would you like to do?
Testing MergeSort
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