Scala: Instrumented Quicksort

It is some times a lot easier to see what an algorithm is doing if print statements are added to the code. Note that each time that the sort function is called recursively the level counter is incremented. the printout is indented one more space for each level (recursion call).

$ scalac -feature MySorter.scala 

$ scala -classpath . MySorter

my sorter

 [1] in: ( ) 6 3 5 2 7 4 8 1

 [1] pivot:  ( ) 7

  [2] in: (>) 6 3 5 2 4 1

  [2] pivot:  (>) 2

   [3] in: (>) 1

   [3] out: (>) 1

   [3] in: (<) 6 3 5 4

   [3] pivot:  (<) 5

    [4] in: (>) 3 4

    [4] pivot:  (>) 4

     [5] in: (>) 3

     [5] out: (>) 3

     [5] in: (<) 

     [5] out: (<) 

   [3] out: (>) 3 4

    [4] in: (<) 6

    [4] out: (<) 6

  [2] out: (<) 3 4 5 6

 [1] out: (>) 1 2 3 4 5 6

  [2] in: (<) 8

  [2] out: (<) 8

[0] out: ( ) 1 2 3 4 5 6 7 8

[0] final: s1 2 3 4 5 6 7 8

// Original code from http://www.scala-lang.org/docu/files/ScalaByExample.pdf

def sort(xs: Array[Int]): Array[Int] = {
  if (xs.length <= 1) xs
  else {
     val pivot = xs(xs.length / 2)
     Array.concat( sort(xs filter (pivot >)), xs filter (pivot ==), sort(xs filter (pivot <)))
  }
}

// Modified code with instrumentation
// compile the code below

import scala.language.postfixOps

object MySorter {

  def indent(len : Int) : String = {
    var sb = new String

    for (i <- 1="" len="" p="" to="">      sb += " "
    }

    return sb
  }

  def printArray[T](level : Int, msg : String, a : Array[T]) {
    val s = a.mkString(" ")
    val padding = indent(level)
    println(padding + "[" + level +  "] "  + msg + s)
  }

  def sort(xs: Array[Int], level : Int, comparison : String): Array[Int] = {
    var l = level
    l += 1

    val padding = indent(l)

    printArray(l, "in: (" + comparison + ") ", xs)
    if (xs.length <= 1) {
      printArray(l, "out: (" + comparison + ") ", xs)
      xs
    }
    else {
      val pivot = xs(xs.length / 2)
      println(padding + "[" + l +  "]"  + " pivot:  (" + comparison + ") " + pivot)
      var out = Array.concat(
        sort(xs filter (pivot >), l, ">"),
        xs filter (pivot ==),
        sort(xs filter (pivot <),l, "<"))
      l -= 1
      printArray(l, "out: (" + comparison + ") ", out)
      return out
    }
  }

  def main(args: Array[String]) {
    println("my sorter")
    var a = Array(6, 3, 5, 2, 7, 4, 8,1)
    var level = 0
    var aa = sort(a, level, " ")
    //printArray(a)
    printArray(0, "final: s", aa)
  }
}