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