insertion sort


See On Github

Data

Source Code

/* SCALA Implementation of Insertion Sort.

  Though the corner cases are covered. But still if you find any additions to it,
  please do add a test for it.

  Any improvements/tests in the code is highly appreciated.
 */

class InsertionSort {
  
  def insertionSort(listToBeSorted: List[Int]): List[Int] = {
    listToBeSorted match {
      case List() => List()
      case x :: xs1 => insertNum(x, insertionSort(xs1))
    }
  }

  def insertNum(x: Int, xs: List[Int]): List[Int] = {
    xs match {
      case List() => List(x)
      case y :: ys => if (x <= y) x :: xs else y :: insertNum(x, ys)
    }
  }
}
import org.scalatest.{Matchers, FunSuite}

class InsertionSortTest extends FunSuite with Matchers {

  test("Insertion Sort should sort") {
    val objectForInsertionSort = new InsertionSort

    objectForInsertionSort.insertionSort(List(1,45,23,89,11)) should be(List(1,11,23,45,89))
    objectForInsertionSort.insertionSort(List(1,1,0,0,3,3,2,2)) should be(List(0,0,1,1,2,2,3,3))
    objectForInsertionSort.insertionSort(List(100,99,98,97,91)) should be(List(91,97,98,99,100))
  }
}