Merge pull request kennyledet#84 from lichtsprung/master

jcla1 · jcla1 · commit 74112965e2f9 · 2013-12-31T06:19:48.000-08:00
added bogo sort in scala
diff --git a/Bogosort/Scala/lichtsprung/bogo_sort.scala b/Bogosort/Scala/lichtsprung/bogo_sort.scala
@@ -0,0 +1,28 @@
+object bogo_sort {
+
+  def sort[T: Ordering](values: Array[T]): Array[T] = {
+    values.permutations foreach {
+      p ⇒
+        if (isSorted(p)) {
+          return p
+        }
+    }
+    values
+  }
+
+  def sort_v2[T: Ordering](values: Array[T]): Array[T] = {
+    values.permutations.find(_.deep == values.sorted.deep).getOrElse(values)
+  }
+
+  private def isSorted[T: Ordering](values: Array[T]): Boolean = {
+    val ord = Ordering[T]
+    import ord._
+
+    for (i ← 1 until values.size) {
+      if (values(i - 1) > values(i)) {
+        return false
+      }
+    }
+    true
+  }
+}
diff --git a/Bogosort/Scala/lichtsprung/bogo_sort_test.scala b/Bogosort/Scala/lichtsprung/bogo_sort_test.scala
@@ -0,0 +1,16 @@
+import org.scalatest.{ Matchers, FlatSpec }
+import bogo_sort._
+
+class bogo_sort_test extends FlatSpec with Matchers {
+  val values = Array(1, 17, -4, 2)
+
+  "Bogo Sort" should "sort an array of Ints" in {
+    val sorted = sort(values)
+    sorted should contain inOrder (-4, 1, 2, 17)
+  }
+
+  "Bogo Sort V2" should "sort an array of Ints by looking for the sorted array in the iterator of all permutations " in {
+    val sorted = sort_v2(values)
+    sorted should contain inOrder (-4, 1, 2, 17)
+  }
+}
