bubble sort


See On Github

Data

Source Code

object bubble_sort {

  /**
    * Functional, iterative version of bubble sort.
    * @param a the array to be sorted
    * @return the sorted copy of a
    */
  def bubble_sort_func[T: Ordering](a: Array[T]): Array[T] = {
    val ord = Ordering[T]
    import ord._

    def swap(x: Int, y: Int, s: Array[T]): Unit = {
      val tmp = s(x)
      s(x) = s(y)
      s(y) = tmp
    }

    val s = a.clone()
    var sorted = true

    for (i ← 0 until s.length) {
      sorted = true

      for (j ← 1 until s.length - i) {
        if (s(j) < s(j - 1)) {
          swap(j, j - 1, s)
          sorted = false
        }
      }

      if (sorted) {
        return s
      }
    }
    s
  }

  /**
    * Iterative, inplace version of bubble sort.
    * @param a the array to be sorted
    */
  def bubble_sort_inplace[T: Ordering](a: Array[T]): Unit = {

    val ord = Ordering[T]
    import ord._

    def swap(x: Int, y: Int, s: Array[T]): Unit = {
      val tmp = s(x)
      s(x) = s(y)
      s(y) = tmp
    }

    var sorted = true
    for (i ← 0 until a.length) {
      sorted = true
      for (j ← 1 until a.length - i) {
        if (a(j) < a(j - 1)) {
          swap(j, j - 1, a)
          sorted = false
        }
      }

      if (sorted) {
        return
      }
    }
  }
}
import org.scalatest.{ Matchers, FlatSpec }
import bubble_sort._

class bubble_sort_test extends FlatSpec with Matchers {
  "Bubble Sort (functional)" should "sort an array and leave the original array unchanged" in {
    val ints = Array(3, 2, 4, 1, 5)
    val sortedInts = bubble_sort_func(ints)
    sortedInts should contain inOrder (1, 2, 3, 4, 5)
    ints should contain inOrder (3, 2, 4, 1, 5)
  }

  "Bubble Sort (inplace)" should "sort an array" in {
    val ints = Array(3, 2, 4, 1, 5)
    bubble_sort_inplace(ints)
    ints should contain inOrder (1, 2, 3, 4, 5)
  }

}