Bubble Sort

Algorithm

Space (if swaps done in place): $O(1)$

Complexity: $O(n^2)$

Implementation

def bs(arr: Vector[Int]): Vector[Int] = {

  @tailrec
  def go(arr: Vector[Int], i: Int, swaps: Boolean): (Vector[Int], Boolean) = {
    if (i == arr.length) arr -> swaps
    else {
      if (arr(i - 1) > arr(i)) {
         go(arr.updated(i, arr(i - 1)).updated(i - 1, arr(i)), i + 1, true
      } else
        go(arr, i + 1, swaps)
    }
  }

  val (res, swaps) = go(arr, 1, false)
  if (!swaps) res
  else bs(res)
}