/dev/shinobi

Here is an implementation of insertion sort using Scala. Learning the ins/outs of Scala idioms and collections.

<

div>

import scala.util._
import scala.collection.mutable._</p>

<p>object InsertSort {</p>

<p>def main(args: Array[String]) : Unit = {
    val list:ListBuffer[Int] = initListWith(args.first.toInt)
    println(&quot;Before: &quot;+list)
    println(&quot;After: &quot;+insertSort(list))
  }</p>

<p>private def insertSort(list:ListBuffer[Int]):ListBuffer[Int] = {
    (1 until list.length).foreach( (i:Int) =&gt; {
      rewindCompare(list, i)
    })<br />
    list
  }</p>

<p>private def rewindCompare(list:ListBuffer[Int], idx:Int):Unit = {
    val value = list(idx)<br />
    def swap(i: Int, j: Int) { val v = list(i); list(i) = list(j); list(j) = v }
    for (revIdx &lt;- idx until 0 by -1) {
      if (value &lt; list(revIdx-1)) swap(revIdx, revIdx-1)
      else return
    }
  }</p>

<p>private def initListWith(limit:Int):ListBuffer[Int] = {
    val list:ListBuffer[Int] = new ListBuffer()
    val randGen = new Random()
    (0 until limit).foreach( i =&gt; list += randGen.nextInt(1000000) )
    return list
  }<br />
}

Compile and run as…

$ scalac InsertionSort.java
$ scala InsertionSort 20

Outputs:

Before: ListBuffer(548915, 963275, 872581, 284656, 52299, 261918, 222533, 288234, 340859, 546783, 428115, 659633, 450991, 693520, 15495, 108540, 402193, 48479, 701302, 269521)

After: ListBuffer(15495, 48479, 52299, 108540, 222533, 261918, 269521, 284656, 288234, 340859, 402193, 428115, 450991, 546783, 548915, 659633, 693520, 701302, 872581, 963275)

Your output will vary, as the initial list which is sorted is generated randomly.

Tags: algorithms, scala

This entry was posted on Sunday, December 27th, 2009 at 11:44 pm and is filed under Uncategorized. You can follow any comments to this entry through the RSS 2.0 feed. You can leave a comment, or trackback from your own site.