Commits

Anonymous committed c3ab910

add test case

Comments (0)

Files changed (3)

src/main/scala/InsertSort.scala

-
-
-object InsertSort {
-
-  def sort[T](less: (T, T) => Boolean)(sorted: List[T], rest: List[T]): List[T] = {
-    def insert(value: T, sorted: List[T]): List[T] = {
-      def _recursive(acc: List[T], xs: List[T]): List[T] = {
-        xs match {
-          case Nil => value :: acc
-          case h :: t =>
-            if (less(value, h)) _recursive(h :: acc, t)
-            else t.reverse ::: List(h, value) ::: acc
-        }
-      }
-      _recursive(Nil, sorted.reverse)
-    }
-
-    rest match {
-      case Nil => sorted
-      case h :: t => sort(less)(insert(h, sorted), t)
-    }
-  }
-
-  def main(args: Array[String]) = {
-    val l = List(10, 8, 2, 6, 5, 1)
-    println(sort((x: Int, y: Int) => x < y)(Nil, l))
-
-    val ll = List(-100, 0, 0, 9, 2, -100)
-    println(sort((x: Int, y: Int) => x < y)(Nil, ll))
-  }
-}
-

src/main/scala/InsertionSort.scala

+
+object InsertionSort {
+
+  def sort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {
+    def _sort(sorted: List[T], rest: List[T]): List[T] = {
+      def insert(value: T, sorted: List[T]): List[T] = {
+        def _recursive(acc: List[T], xs: List[T]): List[T] = {
+          xs match {
+            case Nil => value :: acc
+            case h :: t =>
+              if (less(value, h)) _recursive(h :: acc, t)
+              else t.reverse ::: List(h, value) ::: acc
+          }
+        }
+        _recursive(Nil, sorted.reverse)
+      }
+      rest match {
+        case Nil => sorted
+        case h :: t => _sort(insert(h, sorted), t)
+      }
+    }
+    _sort(Nil, xs)
+  }
+
+  def main(args: Array[String]) = {
+    val l = List(10, 8, 2, 6, 5, 1)
+    println(sort((x: Int, y: Int) => x < y)(l))
+
+    val ll = List(-100, 0, 0, 9, 2, -100)
+    println(sort((x: Int, y: Int) => x < y)(ll))
+  }
+}

src/test/scala/InsertionSort.scala

+import org.scalatest.FlatSpec
+import org.scalatest.matchers.ShouldMatchers
+
+class InsertionSortTest extends FlatSpec with ShouldMatchers {
+
+  val cmp = (x: Int, y: Int) => x < y
+  val intSorterAsc = InsertionSort.sort(cmp) _
+
+  "normal list" should "sortable" in {
+    val xs = List(0, 8, -100, 6, 2, 5)
+    val sorted = intSorterAsc(xs)
+    sorted should equal { xs.sortWith(_ < _) }
+  }
+
+  "empty list" should "return empty" in {
+    val xs = List()
+    intSorterAsc(List()) should equal { List()}
+  }
+}