Finally beeing a bit more serious about learning the Scala language, I wanted to do some exercises to get a little fluent in the language. Because I’m only four Chapters into “Programming in Scala”, I choose the simple one: Implementing search algorithms - today the insertion sort. Here is the the “easy” solution coming from a mostly object-orientated background transcoded from a text book:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def insertionSort(unsortedList : List[String]) = {
    val F = unsortedList.toArray
    for(i <- (2 until F.length)){
      val m = F(i)
      var j = i;
      while(j > 1 && !sorted){
        if (F(j-1) >= m) {
          F(j) = F(j-1)
          j -= 1
        }
      }
      F(j) = m
    }
    F.toList
 }

// Note:
// This algorithm has been transcribed from:
// Saake and Sattler. "Algorithmen und Datenstrukturen. Eine Einführung in Java".
// dpunkt.verlag Heidelberg, 2004. page 123f

So, the program iterates over the indexes of the elements from 2 to unsortedList.lenght (line 3). Then it grabs the element of the current index (line 4) and and checks that all elements bigger than the current one get moved one index higher (line 6-11). The it assigns the current element to the place the last element from has been moved from - and everything is sorted. What I left out from the original algorithm from my source, is a break. This is not critical as the break is a green-cut, to save some performance. This is because scala doesn’t offer a break. This does not really look like scala code. It uses an Array, which is a mutable class - and it uses index based access to a large extend. So I thought about the algorithm and came up (after some trying) with this alternative implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def insertionSort(source : List[String]) = {
  var sorted = List(source.head)
  var unsorted = source.tail
  while(unsorted.tail != Nil){
    val index = sorted.indexWhere( _ > unsorted.head)

    if(index < 0){
      sorted = sorted ::: List(unsorted.head)
    }
    else {
      sorted = sorted.take(index) ::: unsorted.head :: sorted.drop(index)
    }

    unsorted = unsorted.tail
  }
  sorted
}

So first of all, we now have two lists. One with the unsorted and one with the sorted elements. At first the program puts the head of the source list into the sorted list, the tail ends up in the unsorted list (lines 2 and 3). Then it does a while loop until the unsorted list is empty (Nil is an empty list in scala, line 4)- always putting its head into the sorted list and putting its tail in the unsorted list itself, so the unsorted list gets smaller every while-iteration.

The sorting happens based on index (as I understand it, this cannot be avoided in insertion sort, or do you have a solution?). First it finds the index of the first element smaller than the current one (line 5). Then the program creates a new sorted list (the lists are immutable, so we have to create one and assign it to the variable) - with the elements before at the top, the current element in the middle and the elements after at the end (line 11). If the current element is the biggest one (which would mean the index is -1), the element is put at the end (line 8).

So this is my approach. Do you have a better one? Or at least a different one?