Monday, February 22, 2010

QuickSort in Scala

Today I stumbled on this post, showing Quick-Sort impl in various languages.. and I got the itch to impl a simple version for same in scala. Here is the result..
def quickSort[A](xs: List[A])(implicit orderer:(A)=>Ordered[A]): List[A] =
xs match {
case Nil => xs
case _ :: Nil => xs
case x :: rest =>
quickSort(rest.filter(orderer(_) <= x)) ++ List(x) ++
quickSort(rest.filter(orderer(_) > x))
}
Interesting thing to note is that the size is close to same as the Haskell impl in the mentioned post.

A trial run on the Scala REPL..
Welcome to Scala version 2.7.5.final (Java HotSpot(TM) Client VM, Java 1.6.0_07).
Type in expressions to have them evaluated.
Type :help for more information.

scala> def quickSort[A](xs: List[A])(implicit orderer:(A)=>Ordered[A]): List[A] =
xs match {
case Nil => xs
case x :: Nil => xs
case x :: rest =>
quickSort(rest.filter(orderer(_) <= x)) ++ List(x) ++ quickSort(rest.filter(orderer(_) > x))
}
| | | | | | quickSort: [A](List[A])(implicit (A) => Ordered[A])List[A]

scala> quickSort(List(2,2,2,100,-1,2,5,1,0,3,4,3))
res0: List[Int] = List(-1, 0, 1, 2, 2, 2, 2, 3, 3, 4, 5, 100)

scala> quickSort(List("himanshu","ruchi","nitin","manoj"))
res1: List[java.lang.String] = List(himanshu, manoj, nitin, ruchi)