How to implement tail recursive fast sort in Scala

Question

I wrote a recursive version:

def quickSort[T](xs: List[T])(p: (T, T) => Boolean): List[T] = xs match{ case Nil => Nil case _ => val x = xs.head val (left, right) = xs.tail.partition(p(_, x)) val left_sorted = quickSort(left)(p) val right_sorted = quickSort(right)(p) left_sorted ::: (x :: right_sorted) } 

But I do not know how to change it to a ponytail. Can anyone give me a suggestion?

Answer 1

Any recursive function can be converted to use a heap, not a stack, to track context. This process is called trampolining .

Here's how to do it with Scalaz.

 object TrampolineUsage extends App { import scalaz._, Scalaz._, Free._ def quickSort[T: Order](xs: List[T]): Trampoline[List[T]] = { assert(Thread.currentThread().getStackTrace.count(_.getMethodName == "quickSort") == 1) xs match { case Nil => return_ { Nil } case x :: tail => val (left, right) = tail.partition(_ < x) suspend { for { ls <- quickSort(left) rs <- quickSort(right) } yield ls ::: (x :: rs) } } } val xs = List.fill(32)(util.Random.nextInt()) val sorted = quickSort(xs).run println(sorted) val (steps, sorted1) = quickSort(xs).foldRun(0)((i, f) => (i + 1, f())) println("sort took %d steps".format(steps)) } 

Of course, you need either a very large structure or a really small stack in order to have a practical problem with the algorithm without tail-recursive separation and subjugation, since you can handle 2 ^ N elements with a stack depth of N.

http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

UPDATE

scalaz.Trampoline is a special case of a (much) more general structure, Free . It is defined as type Trampoline[+A] = Free[Function0, A] . In fact, you can write quickSort more general, so it is parameterized by the type constructor used in Free . This example shows how this is done, and how you can use the same code for binding using a stack, heap, or at the same time.

https://github.com/scalaz/scalaz/blob/scalaz-seven/example/src/main/scala/scalaz/example/TrampolineUsage.scala

Answer 2

Tail recursion requires that you do the work, both completed and work in progress, forward at every step. So you just need to encapsulate your work in a heap, not a stack. You can use the list as a stack to make it simple enough. Here is the implementation:

 def quicksort[T](xs: List[T])(lt: (T,T) => Boolean) = { @annotation.tailrec def qsort(todo: List[List[T]], done: List[T]): List[T] = todo match { case Nil => done case xs :: rest => xs match { case Nil => qsort(rest, done) case x :: xrest => val (ls, rs) = (xrest partition(lt(x,_))) if (ls.isEmpty) { if (rs.isEmpty) qsort(rest, x :: done) else qsort(rs :: rest, x :: done) } else qsort(ls :: List(x) :: rs :: rest, done) } } qsort(List(xs),Nil) } 

This, of course, is just a special case of tracing associated with retronym (where you don't need to pass the function forward). Fortunately, this case is quite easy to do manually.

Answer 3

I just wrote this article that provides step-by-step instructions on how to convert a classic Quicksort implementation to a tail recursive form:

Quicksort rewritten in tail recursive form - example in Scala

I hope you will enjoy!