Welcome to BigData School that can get you hired on Small startups or big Product based companies.Are you tired of 30-40 hours of theoritical bigdata courses in the market. Welcome to 240+ hours of Bigdata training. Just subscribe to our popup to get access to our 80+hours of course absolutely free.Try them out and you can join our further course once you are happy with our Demos.

Insertion Sort

Big Data    On Thursday 22nd of June 2017 12:10:06 PM By Suraz Ghimire
Logic:
start from index 1 to N,
for element at index 1, search 1 till 0, and keep swapping until the left side of array is completedly sorted.
for element at index say 5, search from 5 to 0, and keep swapping until the left side of array is completedly sorted.

At each iteration, you will always loop backward  and keep sorting.

val arr=Array(25,15,30,5,10,20 )

iteration 1: consider only 25. It is already sorted.No change
iteration 2: consider 15. Now you have 2 part of array left side(25,15) and right side (30,5,10,20)
15 is not sorted wrt 25, so exchange and let it become (15,25)
arr= 15,25, 30,5,10,20
iteration 3: consider 30. Now we have part 1 15,25,30 and part 2 5,10,20. Part 1 is already sorted no change
iteration 4: consider 5. Now we have part 1 . 15,25,30,5 and part2 10,20.
start from the reverse and keep 5 in the right place, hence it will become 5,15,25,30,5
continue doing so.

package sorting.sorting

object InsertionSort {

def main(args: Array[String]): Unit = {
val arr=Array(25,15,30,5,10,20 )
sort(arr)
arr.foreach(println)

}

def sort(arr:Array[Int])={

for(i<- 1 until arr.length){
val num=arr(i)
var j=i-1
println(s"Currently Processing $num")
while(j>=0 && arr(j)>num){
println(s"${arr(j)}>$num :shift")
arr(j+1)=arr(j)
j-=1
}
println(s"Place $num at arr(${j+1})")
arr(j+1)=num
}
}
}

Output:

Currently Processing 15
25>15 :shift
Place 15 at arr(0)
Currently Processing 30
Place 30 at arr(2)
Currently Processing 5
30>5 :shift
25>5 :shift
15>5 :shift
Place 5 at arr(0)
Currently Processing 10
30>10 :shift
25>10 :shift
15>10 :shift
Place 10 at arr(1)
Currently Processing 20
30>20 :shift
25>20 :shift
Place 20 at arr(3)
5
10
15
20
25
30





About Author

Suraz Ghimire