quickSelect

quickSelects.scala

import org.scalacheck.Properties
import org.scalacheck.Prop.{forAll, BooleanOperators}
import scala.util.Random

def quickSelect[A <% Ordered[A]](seq: Seq[A], n: Int, rand: Random = new Random): A = {
  val pivot = rand.nextInt(seq.length);
  val (left, right) = seq.partition(_ < seq(pivot))
  if (left.length == n) {
    seq(pivot)
  } else if (left.length < n) {
    quickSelect(right, n - left.length, rand)
  } else {
    quickSelect(left, n, rand)
  }
}

def myQS[T <% Ordered[T]](s: Seq[T], k: Int): T = {
  val pivot = s(0)
  val (left, right) = s.slice(1, s.length).partition(_ < pivot)
  if (left.length == k) {
    pivot
  } else if (left.length < k) {
    myQS(right, k - left.length - 1)
  } else {
    myQS(left, k)
  }
}

def kth[T <% Ordered[T]](s: Seq[T], k: Int): T = {
  s.sorted.apply(k)
}

object QSSpec extends Properties("QS") {
  property("EqualsRef") = forAll { (k: Int, s: Seq[Int]) =>
    println(k, s)
    (k >= 0 && k < s.length) ==> (kth(k, s) == quickSelect(s, k))
  }
}

object MyQSSpec extends Properties("QS") {
  property("EqualsRef") = forAll { (k: Int, s: Seq[Int]) =>
    (k >= 0 && k < s.length) ==> (kth(k, s) == myQS(s, k))
  }
}