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 currying
object 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, 5
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(), 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



.

No comments: