## Monday, 19 January 2009

### Scala, insertion sort and pattern matching

This posting shows insertion sorting in Scala. Insertion sort is not a particularly efficient algorithm but this example code does demonstrate the use of pattern matching on lists using the match keyword and the case x :: y type expression.

`val result = values match { case List() => List() case value :: valuesTail => insert(value, iSort(valuesTail))}`

The above code pattern matched the List values against 2 cases. The first being the empty list, in which case an empty list List() is returned. the second is the pattern value :: valuesTail, which puts the head of the list in value and the tail (the rest of the list) in valuesTail.

Example code:

`package test// Nb: This is not an efficient sorting algorithm but it domostrates// some aspects of scala for representing algorithms, along with functions as first class objects and curryingobject SortingTest {   def main(args : Array[String]) {       val list1 = 5 :: 2 :: 3 :: 1 :: 0 :: -1 :: 2 :: Nil       val matcher = (x : Int, y : Int) => x < y       val sortedList = insertionSort(list1, matcher)       println("sortedList = " + sortedList.mkString(", "))       val revMatcher = (x : Int, y : Int) => x >= y       val revSortedList = insertionSort(list1, revMatcher)       println("revSortedList = " + revSortedList.mkString(", "))   }   def insertionSort(values : List[Int], matcher : (Int, Int) => Boolean) : List[int] = {       def iSort(values : List[Int]) : List[int] = {           val result = values match {               case List() => List()               case value :: valuesTail => insert(value, iSort(valuesTail))           }           println("iSort called with " + values + ", result = " + result)           result       }       def insert(value : Int, values : List[Int]) : List[Int] = {           val result = values match {               // if list is empty return new list with single element in it               case List() => List(value)               // otherwise insert into list in order, recursively               case x :: xTail =>                   if (matcher(value, x)) {                       value :: values                   }                   else {                       x :: insert(value, xTail)                   }           }                     println("insert called with " + value + ", values " + values + ", result = " + result)           result       }       iSort(values)   }}`

Results:

If you run the above example code the results are as follows:

`iSort called with List(), result = List()insert called with 2, values List(), result = List(2)iSort called with List(2), result = List(2)insert called with -1, values List(2), result = List(-1, 2)iSort called with List(-1, 2), result = List(-1, 2)insert called with 0, values List(2), result = List(0, 2)insert called with 0, values List(-1, 2), result = List(-1, 0, 2)iSort called with List(0, -1, 2), result = List(-1, 0, 2)insert called with 1, values List(2), result = List(1, 2)insert called with 1, values List(0, 2), result = List(0, 1, 2)insert called with 1, values List(-1, 0, 2), result = List(-1, 0, 1, 2)iSort called with List(1, 0, -1, 2), result = List(-1, 0, 1, 2)insert called with 3, values List(), result = List(3)insert called with 3, values List(2), result = List(2, 3)insert called with 3, values List(1, 2), result = List(1, 2, 3)insert called with 3, values List(0, 1, 2), result = List(0, 1, 2, 3)insert called with 3, values List(-1, 0, 1, 2), result = List(-1, 0, 1, 2, 3)iSort called with List(3, 1, 0, -1, 2), result = List(-1, 0, 1, 2, 3)insert called with 2, values List(3), result = List(2, 3)insert called with 2, values List(2, 3), result = List(2, 2, 3)insert called with 2, values List(1, 2, 3), result = List(1, 2, 2, 3)insert called with 2, values List(0, 1, 2, 3), result = List(0, 1, 2, 2, 3)insert called with 2, values List(-1, 0, 1, 2, 3), result = List(-1, 0, 1, 2, 2, 3)iSort called with List(2, 3, 1, 0, -1, 2), result = List(-1, 0, 1, 2, 2, 3)insert called with 5, values List(), result = List(5)insert called with 5, values List(3), result = List(3, 5)insert called with 5, values List(2, 3), result = List(2, 3, 5)insert called with 5, values List(2, 2, 3), result = List(2, 2, 3, 5)insert called with 5, values List(1, 2, 2, 3), result = List(1, 2, 2, 3, 5)insert called with 5, values List(0, 1, 2, 2, 3), result = List(0, 1, 2, 2, 3, 5)insert called with 5, values List(-1, 0, 1, 2, 2, 3), result = List(-1, 0, 1, 2, 2, 3, 5)iSort called with List(5, 2, 3, 1, 0, -1, 2), result = List(-1, 0, 1, 2, 2, 3, 5)sortedList = -1, 0, 1, 2, 2, 3, 5iSort called with List(), result = List()insert called with 2, values List(), result = List(2)iSort called with List(2), result = List(2)insert called with -1, values List(), result = List(-1)insert called with -1, values List(2), result = List(2, -1)iSort called with List(-1, 2), result = List(2, -1)insert called with 0, values List(-1), result = List(0, -1)insert called with 0, values List(2, -1), result = List(2, 0, -1)iSort called with List(0, -1, 2), result = List(2, 0, -1)insert called with 1, values List(0, -1), result = List(1, 0, -1)insert called with 1, values List(2, 0, -1), result = List(2, 1, 0, -1)iSort called with List(1, 0, -1, 2), result = List(2, 1, 0, -1)insert called with 3, values List(2, 1, 0, -1), result = List(3, 2, 1, 0, -1)iSort called with List(3, 1, 0, -1, 2), result = List(3, 2, 1, 0, -1)insert called with 2, values List(2, 1, 0, -1), result = List(2, 2, 1, 0, -1)insert called with 2, values List(3, 2, 1, 0, -1), result = List(3, 2, 2, 1, 0, -1)iSort called with List(2, 3, 1, 0, -1, 2), result = List(3, 2, 2, 1, 0, -1)insert called with 5, values List(3, 2, 2, 1, 0, -1), result = List(5, 3, 2, 2, 1, 0, -1)iSort called with List(5, 2, 3, 1, 0, -1, 2), result = List(5, 3, 2, 2, 1, 0, -1)revSortedList = 5, 3, 2, 2, 1, 0, -1`

.