CODEWITHSUNDEEP
algorithmscaladata-structurestail-recursion
爱国者
爱国者

Reputation: 4328

How to implement tail-recursive quick sort in Scala

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 don't know how to change it into tail-recurisive. Can anyone give me a suggestion ?

Upvotes: 4

Views: 3822

Answers (4)

Alexander Albul
Alexander Albul

Reputation: 11

One more version using tailrec, pattern matching and implicit ordering:

  def sort[T](list: List[T])(implicit ordering: Ordering[T]): List[T] = {
    @scala.annotation.tailrec
    def quickSort(todo: List[List[T]], accumulator: List[T]): List[T] = todo match {
      case Nil => accumulator
      case head :: rest => head match {
        case Nil => quickSort(rest, accumulator)
        case pivot :: others =>
          others.partition(ordering.lteq(_, pivot)) match {
            case (Nil, Nil) => quickSort(rest, pivot :: accumulator)
            case (Nil, larger) => quickSort(larger :: rest, pivot :: accumulator)
            case (smaller, larger) => quickSort(smaller :: List(pivot) :: larger :: rest, accumulator)
          }
      }
    }
    quickSort(List(list), Nil)
  }

  val sorted = sort(someValues)
  val reverseSorted = sort(someIntValues)(Ordering[Int].reverse)

Upvotes: 1

0xReinventor
0xReinventor

Reputation: 41

I just wrote this article which contains step by step instructions on how to convert the classic implementation of Quicksort to tail-recursive form:

Quicksort rewritten in tail-recursive form - An example in Scala

I hope you find it interesting!

Upvotes: 4

Rex Kerr
Rex Kerr

Reputation: 167881

Tail recursion requires you to pass work, both completed and work-to-do, forward on each step. So you just have to encapsulate your work-to-do on the heap instead of the stack. You can use a list as a stack, so that's easy enough. Here's an 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 is, of course, just a special case of trampolining as linked to by retronym (where you don't need to pass the function forward). Fortunately, this case is easy enough to do by hand.

Upvotes: 10

retronym
retronym

Reputation: 55028

Any recursive function can be be converted to use the heap, rather than the stack, to track the context. The process is called trampolining.

Here's how it could be implemented 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 really big structure or a really small stack to have a practical problem with a non-tail-recursive divide and conquer algorithm, as 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's defined as type Trampoline[+A] = Free[Function0, A]. It's actually possible to write quickSort more generically, so it is parameterized by the type constructor used in Free. This example shows how this is done, and how you can then use the same code to bind using the stack, the heap, or in concurrently.

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

Upvotes: 15

Related Questions