ScalaのAdvanced Exampleを写経する(9)-imperative quicksort

クイックソートのimperativeスタイル。
imperativeは命令的。逐次ってことかな。
要は関数的でない従来の方法でのソート。
関数的なサンプルは別に用意されているので、次の機会でもやってみる。
sort.scala | The Scala Programming Language

package sample.snippet

/** Quick sort, imperative style. */
object sort {
  
  def sort(a: Array[Int]) {
    
    def swap(i: Int, j: Int) {
      val t = a(i)
      a(i) = a(j)
      a(j) = t
    }
    
    def sort1(l: Int, r:Int) {
      val pivot = a((l + r) / 2)
      var i = l
      var j = r
      while(i <= j) {
        while (a(i) < pivot) i += 1
        while (a(j) > pivot) j -= 1
        if (i <= j){
          swap(i, j)
          i += 1
          j -= 1
        }
      }
      Console.println("途中経過" + "l:" + l + "r:" + r + "i:" + i + "j:" + j)
      Console.println(a.toString())
      if (l < j) sort1(l, j)
      if (j < r) sort1(i, r)
    }
    
    if (a.length > 0)
      sort1(0, a.length - 1)
    
  }
  
  def println(ar: Array[Int]) {
    def print1 = {
      def iter(i: Int): String =
        ar(i) + (if (i < ar.length - 1) "," + iter(i+1) else "")
      if (ar.length == 0) "" else iter(0)
    }
    Console.println("[" + print1 + "]")
  }
  
  def main(args: Array[String]) {
    val ar = Array(6,2,8,5,1)
    println(ar)
    sort(ar)
    println(ar)

    val ar1 = Array(6,2,8,5,1,7,3,4)
    println(ar1)
    sort(ar1)
    println(ar1)
  }
}

関数をネストさせることができる。
ネストした関数からは外の関数に定義されている変数を参照することができる。
ここでは、配列aをネストした関数swapやsort1から参照してる。

実行結果。

[6,2,8,5,1]
途中経過l:0r:4i:4j:3
Array(6, 2, 1, 5, 8)
途中経過l:0r:3i:2j:0
Array(1, 2, 6, 5, 8)
途中経過l:2r:3i:3j:2
Array(1, 2, 5, 6, 8)
途中経過l:3r:3i:4j:2
Array(1, 2, 5, 6, 8)
途中経過l:4r:3i:4j:3
Array(1, 2, 5, 6, 8)
途中経過l:4r:4i:5j:3
Array(1, 2, 5, 6, 8)
途中経過l:5r:4i:5j:4
Array(1, 2, 5, 6, 8)
[1,2,5,6,8]
[6,2,8,5,1,7,3,4]
途中経過l:0r:7i:4j:3
Array(4, 2, 3, 1, 5, 7, 8, 6)
途中経過l:0r:3i:2j:0
Array(1, 2, 3, 4, 5, 7, 8, 6)
途中経過l:2r:3i:3j:1
Array(1, 2, 3, 4, 5, 7, 8, 6)
途中経過l:3r:3i:4j:2
Array(1, 2, 3, 4, 5, 7, 8, 6)
途中経過l:4r:3i:4j:3
Array(1, 2, 3, 4, 5, 7, 8, 6)
途中経過l:4r:7i:6j:5
Array(1, 2, 3, 4, 5, 6, 8, 7)
途中経過l:4r:5i:5j:3
Array(1, 2, 3, 4, 5, 6, 8, 7)
途中経過l:5r:5i:6j:4
Array(1, 2, 3, 4, 5, 6, 8, 7)
途中経過l:6r:5i:6j:5
Array(1, 2, 3, 4, 5, 6, 8, 7)
途中経過l:6r:7i:7j:6
Array(1, 2, 3, 4, 5, 6, 7, 8)
途中経過l:7r:7i:8j:6
Array(1, 2, 3, 4, 5, 6, 7, 8)
途中経過l:8r:7i:8j:7
Array(1, 2, 3, 4, 5, 6, 7, 8)
[1,2,3,4,5,6,7,8]