Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Lazy Quicksort in Scala

Is it possible to do this sort of thing in Scala?

like image 591
Mahesh Avatar asked Apr 22 '10 13:04

Mahesh


1 Answers

def quicksort[A](xs: Stream[A])(implicit o: Ordering[A]): Stream[A] = {
  import o._ 
  if (xs.isEmpty) xs else {
      val (smaller, bigger) = xs.tail.partition(_ < xs.head)
      quicksort(smaller) #::: xs.head #:: quicksort(bigger)
  }
}

It can be done with views as well, though it's bound to be much slower:

def quicksort[A](xs: List[A])(implicit o: Ordering[A]) = {
  import o._
  def qs(xs: SeqView[A, List[A]]): SeqView[A, Seq[_]] = if (xs.isEmpty) xs else {
    val (smaller, bigger) = xs.tail.partition(_ < xs.head)
    qs(smaller) ++ (xs.head +: qs(bigger))
  }
  qs(xs.view)
}
like image 161
Daniel C. Sobral Avatar answered Oct 13 '22 01:10

Daniel C. Sobral



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!