Bubble sort in Scala

I wanted to implement a bubble sort in Scala following the steps described in: http://www.bbc.co.uk/education/guides/z22wwmn/revision/3

import scala.collection.mutable.MutableList

val result = bubbleSort(List(3,2,4,1,5))

def bubbleSort(list: List[Int]): (List[Int]) = {
  def doIteration(list: List[Int]): (List[Int], Boolean) = {
    val mutableList = MutableList(list: _*)
    val numberOfPairs = 0 until mutableList.length - 1
    for (pair  list(pair + 1)) {
        val tempOld = list(pair + 1)
        mutableList(pair + 1) = list(pair)
        mutableList(pair) = tempOld
      }
    }
    val hasSwaps = list != mutableList.toList
    (mutableList.toList, hasSwaps)
  }

  var result = doIteration(list)
  while(result._2){
    result = doIteration(result._1)
  }
  result._1
}

I am aware I have used a few things which are not idiomatic in Scala such as:

• MutableList

• while loop

• var

I would appreciate suggestions for incremental improvements to make the code more functional and idiomatic Scala.

Below I've written up an implementation of a recursive bubble sort that addresses the main concerns you mentioned. The areas your code can be improved matches what you instinctively pointed out in your bullet points.

Whenever you use a List or MutableList in Scala remember that it is in fact a linked list and so accessing an element takes linear time. This could add a significant number of operations to an implementation of bubble sort that utilizes a List. As a substitute I used an Array which offers constant time access to elements. It is also worth mentioning that the Array container is mutable in Scala even if it is declared as a val.

We can kill two birds with one stone by rewriting the while loop as a recursive procedure. The two birds are while and var and our trusty stone is recursion.

def bubbleSort(arr: Array[Int]): Array[Int] = {

  val hasSwaps = 
    for {
      i  arr(i)) {
        val tmp    = arr(i)
        arr(i)     = arr(i - 1)
        arr(i - 1) = tmp
        true
      }
      else false
    }

  if (hasSwaps.reduce(_ || _)) bubbleSort(arr)
  else arr
}

StackExchange Code Review Q#108316, answer score: 3