Insertion Sort in Scala
Insertion sort is a so much simple and straightforward sorting algorithm. The pseudocode looks like following:
for j ← 2 to length[A]
do key ← A[j]
i ← j - 1
while i > 0 and A[i] > key
do A[i + 1] ← A[i]
i ← i - 1
A[i + 1] ← key
But do it in Scala using FP is a quite interesting experience.
Firstly, the traditional way in Scala:
def insertSort(list:Array[Int]) = {
var j = 1
while(j<list.length){
val key = list(j)
var i = j-1
while(i>=0 && list(i)>key){
list(i+1) = list(i)
i=i-1
}
list(i+1)=key
println("In the middle " + list.mkString(","))
j=j+1
}
list
}
I use
while rather than for, because for means more than looping.The pure functional way requires no side-effect, which also generally means immutable and no loop.
So the first function is
insert(list:List[Int], t:Int]:List[Int], which inserts a value t into a sorted list list and returns the result.
def insert(list:List[Int], t:Int):List[Int]= list match {
case Nil => List[Int](t)
case x::r if x > t=> t::x::r
case x::r => x::insert(r,t)
}
Pattern match makes this like a breeze.
Then the sorting function:
def insertSortFp(list:List[Int])={
(list :\ List[Int]())((a,b)=>insert(b,a))
}
I use
foldRight here just because of my laziness.
