Insertion Sort [Iterative]
12345678910111213141516171819202122232425262728293031323334353637
object Main extends App {
def insertionSort1(arr: Array[Int]): Array[Int] = {
for (i <- 0 until arr.size) {
val key = arr(i);
var j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr(j) > key)
{
arr(j+1) = arr(j)
j = j-1;
}
arr(j+1) = key;
}
arr
}
def insertionSort2(array: Array[Int]): Array[Int] = {
for(i <- 0 until array.length){
val hold = array(i)
var holePos = i
while(holePos > 0 && hold < array(holePos - 1)){
array(holePos) = array(holePos - 1)
holePos -= 1
}
array(holePos) = hold
}
array
}
println(insertionSort1(Array(1,2,2,3,1,-10,2,200)).toList)
println(insertionSort2(Array(1,2,2,3,1,-10,2,200)).toList)
}
Scala
INFO