Skip to content

Instantly share code, notes, and snippets.

@bfdes

bfdes/SortingSpec.scala

Last active Oct 25, 2020
Embed
What would you like to do?
Testing MergeSort
import scala.reflect.classTag
import scala.reflect.ClassTag
import org.scalacheck._
import Sorting._
import Histogram
class Histogram[K](keys: Seq[K]) {
private val underlying =
keys.foldLeft(Map.empty[K, Int]) { (m, k) =>
val count = m.getOrElse(k, 0) + 1
m + (k -> count)
}
override def equals(that: Any): Boolean =
that match {
case h: Histogram[K] =>
h.underlying.equals(underlying)
case _ => false
}
override def hashCode: Int = underlying.hashCode
}
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 = {
val indices = 0 until a.length-1
val shifted = 1 until a.length
indices
.zip(shifted)
.forall { case (i, j) => o.lteq(a(i), a(j)) }
}
}
object SortingSpec extends Properties("mergeSort") {
type Pair = (Int, Int) // a type alias
val unsaturated: Gen[Array[Int]] =
Gen.containerOf[Array, Int](Gen.posNum[Int])
val saturated: Gen[Array[Int]] = {
// One possible way of saturating the array with duplicate keys
val sized = Gen.sized(s => Gen.choose(0, Math.sqrt(s).toInt))
Gen.containerOf[Array, Int](sized)
}
val pairs: Gen[Array[Pair]] = {
val n = Gen.choose(0, 5)
val pair = for {
i <- n
j <- n
} yield (i, j) // Syntax sugar for n.flatMap(i => n.map(j => (i, j)))
Gen.containerOf[Array, Pair](pair)
}
property("isSorted") = Prop.forAll(unsaturated) { a =>
mergeSort(a)
isSorted(a)
}
property("keys") = Prop.forAll(unsaturated) { a =>
val before = new Histogram(a)
mergeSort(a)
val after = new Histogram(a)
before == after
}
property("isStable") = Prop.forAll(pairs) { a =>
val byI = Ordering.by[Pair, Int](_._1)
val byJ = Ordering.by[Pair, Int](_._2)
mergeSort(a)(classTag[Pair], byJ)
mergeSort(a)(classTag[Pair], byI)
isSorted(a)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.