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

.