3
\$\begingroup\$

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 <- numberOfPairs) {
      if (list(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.

\$\endgroup\$
  • 2
    \$\begingroup\$ I think that Bubble Sort is inherently imperative, and doesn't lend itself well to FP. There are little things you could improve, but I don't think it's a worthwhile exercise to try to do too much better. Instead, try implementing Selection Sort or Mergesort, they play much nicer with the functional paradigm. \$\endgroup\$ – MattPutnam Oct 21 '15 at 20:57
3
\$\begingroup\$

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 <- (1 until arr.length) 
    } yield {
      if (arr(i - 1) > 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
}
\$\endgroup\$
  • \$\begingroup\$ Isnt using a mutable array the same functional violation as mutable list? My gut tells me this should be using a high order function if immutability was desired which seems to be the case. \$\endgroup\$ – Usman Mutawakil Jun 8 '17 at 1:13
2
\$\begingroup\$

[Disclaimer] This review does not address algorithmic issues. Indeed it dismisses them as inappropriate. To avoid confusion, it should be considered a partial review.

Two Conflicting Goals

At the level of abstraction where the choice to use Scala makes sense and discussions about idiomatic Scala make sense, the idea of implementing a bubble sort does not. The decision to use or not use Scala is typically based on programmer efficiency. Decisions over sorting algorithms are typically based on computational resource efficiency and raw execution speed of critical sections.

Idiomatic Scala is a State of Mind

Trust in the JVM and faith in the sound engineering practice of profiling code before worrying about tuning performance is part and parcel of a wise decision to use Scala or similar languages. We've given up micromanaging memory for a garbage collector and high level abstractions.

Despite the Curly Braces

Scala is not C. Applying "Fortran in any language" with C in Scala will not produce idiomatic Scala. Applying it with Scheme won't either. Writing Ruby in Scala is closer to the mark.

Only Write Code that Matters

The idiomatic Scala would look something like:

scala> List(3,2,4,1,5).sorted
res42: List[Int] = List(1, 2, 3, 4, 5)

Because less code is often easier to understand and might contain fewer bugs...at least those tend to be reasons given for using high level languages since the days when assembly was considered high level and compared to raw machine code it was.

Trust and Verify(maybe)

Idiomatic Scala will rely on library routines such as sorted rather than reinventing them. Mainly because the odds of a random Scala programmer writing a better implementation are approximately zero. Even those who possibly could will not unless there is a verified performance issue and the bottleneck is in the sort. And then it's probably time to look at JVM Bytecode instead of trying to get more efficiency through the Scala compiler.

Advice

  1. Don't write Scala modelled on C or Java.
  2. Take advantage of Scala's high level features.
  3. Don't optimize what doesn't need to be optimized.
  4. Implement procedural code in languages where it is idiomatic.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.