package object quickSelect {
  // (Pseudo)random number generator with a fixed seed so that
  // error situations can be reproduced easier
  val rand = new scala.util.Random(21)

  /**
   * Find the k:th smallest (0 for the smallest) element in
   * the integer sequence seq by using the quickselect algorithm.
   */
  def find(seq: Seq[Int], k: Int): Int = {
    require(0 <= k && k < seq.length)
    // Make a working copy of the sequence as we cannot modify the argument sequence
    val a: Array[Int] = seq.toArray

    def swap ( a : Array[Int], i:Int, j:Int): Unit = {
      val t = a(i); a(i) = a(j); a(j) = t
    }

    def partition(a:Array[Int], lo: Int, hi: Int): (Int, Int) = {
      val random = lo + rand.nextInt(hi - lo)
      var pivot = a(random)
      swap(a, lo, random)
      var i = lo + 1
      var lt = lo
      var gt = hi
      while(i <= gt){
        if(a(i) < pivot) {
          swap(a, lt, i)
          lt = lt + 1
          i = i + 1
        }else if(a(i) > pivot){
          swap(a, i, gt)
          gt = gt - 1
        }else i = i + 1
      }
      (gt, lt)
    }

    def select(a: Array[Int], left: Int, right: Int, k: Int): Int = {
      var lo = left
      var hi = right
      while(lo <= hi){
        if(lo == hi) return a(lo)
        val pvtIndx = partition(a, lo, hi)
        if(k > pvtIndx._1) lo = pvtIndx._1 + 1
        else if(k < pvtIndx._2) hi = pvtIndx._2 - 1
        else return a(pvtIndx._2)
      }
      return -1   //code never reaches here
    }

    return select(a, 0, a.length - 1, k)
  }
}