Selection sort in functional Scala

Question

I'm making my way through "Programming in Scala" and wrote a quick implementation of the selection sort algorithm. However, since I'm still a bit green in functional programming, I'm having trouble translating to a more Scala-ish style. For the Scala programmers out there, how can I do this using Lists and vals rather than falling back into my imperative ways?

http://gist.github.com/225870

Answer 1

As starblue already said, you need a function that calculates the minimum of a list and returns the list with that element removed. Here is my tail recursive implementation of something similar (as I believe foldl is tail recursive in the standard library), and I tried to make it as functional as possible :). It returns a list that contains all the elements of the original list (but kindof reversed - see the explanation below) with the minimum as a head.

def minimum(xs: List[Int]): List[Int] =
  (List(xs.head) /: xs.tail) {
    (ys, x) =>
      if(x < ys.head) (x :: ys)
      else            (ys.head :: x :: ys.tail)
  }

This basically does a fold, starting with a list containing of the first element of xs If the first element of xs is smaller than the head of that list, we pre-append it to the list ys. Otherwise, we add it to the list ys as the second element. And so on recursively, we've folded our list into a new list containing the minimum element as a head and a list containing all the elements of xs (not necessarily in the same order) with the minimum removed, as a tail. Note that this function does not remove duplicates.

After creating this helper function, it's now easy to implement selection sort.

def selectionSort(xs: List[Int]): List[Int] =  
  if(xs.isEmpty) List()
  else {
    val ys = minimum(xs)
    if(ys.tail.isEmpty) 
      ys
    else
      ys.head :: selectionSort(ys.tail)
  }

Unfortunately this implementation is not tail recursive, so it will blow up the stack for large lists. Anyway, you shouldn't use a O(n^2) sort for large lists, but still... it would be nice if the implementation was tail recursive. I'll try to think of something... I think it will look like the implementation of a fold.

Tail Recursive!

To make it tail recursive, I use quite a common pattern in functional programming - an accumulator. It works a bit backward, as now I need a function called maximum, which basically does the same as minimum, but with the maximum element - its implementation is exact as minimum, but using > instead of <.

def selectionSort(xs: List[Int]) = {
  def selectionSortHelper(xs: List[Int], accumulator: List[Int]): List[Int] =
    if(xs.isEmpty) accumulator
    else {
          val ys = maximum(xs)
          selectionSortHelper(ys.tail, ys.head :: accumulator)
    }

  selectionSortHelper(xs, Nil) 
  }

EDIT: Changed the answer to have the helper function as a subfunction of the selection sort function.

It basically accumulates the maxima to a list, which it eventually returns as the base case. You can also see that it is tail recursive by replacing accumulator by throw new NullPointerException - and then inspect the stack trace.

Here's a step by step sorting using an accumulator. The left hand side shows the list xs while the right hand side shows the accumulator. The maximum is indicated at each step by a star.

64* 25 12 22 11  ------- Nil
11 22 12 25*     ------- 64
22* 12 11        ------- 25 64
11 12*           ------- 22 25 64
11*              ------- 12 22 25 64
Nil              ------- 11 12 22 25 64

The following shows a step by step folding to calculate the maximum:

maximum(25 12 64 22 11)

25 :: Nil         /: 12 64 22 11  -- 25 > 12, so it stays as head
25 :: 12          /: 64 22 11     -- same as above
64 :: 25 12       /: 22 11        -- 25 < 64, so the new head is 64
64 :: 22 25 12    /: 11           -- and stays so
64 :: 11 22 25 12 /: Nil          -- until the end

64 11 22 25 12

Answer 2

here is another implementation of selection sort (generic version).

def less[T <: Comparable[T]](i: T, j: T) = i.compareTo(j) < 0

def swap[T](xs: Array[T], i: Int, j: Int) { val tmp = xs(i); xs(i) = xs(j); xs(j) = tmp }

def selectiveSort[T <: Comparable[T]](xs: Array[T]) {
    val n = xs.size
    for (i <- 0 until n) {
        val min = List.range(i + 1, n).foldLeft(i)((a, b) => if (less(xs(a), xs(b))) a else b)
        swap(xs, i, min)
    }
  }     

Answer 3

You should have problems doing selection sort in functional style, as it is an in-place sort algorithm. In-place, by definition, isn't functional.

The main problem you'll face is that you can't swap elements. Here's why this is important. Suppose I have a list (a₀ ... a_x ... a_n), where a_x is the minimum value. You need to get a_x away, and then compose a list (a₀ ... a_x-1 a_x+1 a_n). The problem is that you'll necessarily have to copy the elements a₀ to a_x-1, if you wish to remain purely functional. Other functional data structures, particularly trees, can have better performance than this, but the basic problem remains.

Answer 4

You need a helper function which does the selection. It should return the minimal element and the rest of the list with the element removed.

Answer 5

I think it's reasonably feasible to do a selection sort in a functional style, but as Daniel indicated, it has a good chance of performing horribly.

I just tried my hand at writing a functional bubble sort, as a slightly simpler and degenerate case of selection sort. Here's what I did, and this hints at what you could do:

define bubble(data)
  if data is empty or just one element: return data;
  otherwise, if the first element < the second,
    return first element :: bubble(rest of data);
    otherwise, return second element :: bubble(
      first element :: (rest of data starting at 3rd element)).

Once that's finished recursing, the largest element is at the end of the list. Now,

define bubblesort [data]
  apply bubble to data as often as there are elements in data.

When that's done, your data is indeed sorted. Yes, it's horrible, but my Clojure implementation of this pseudocode works.

Just concerning yourself with the first element or two and then leaving the rest of the work to a recursed activity is a lisp-y, functional-y way to do this kind of thing. But once you've gotten your mind accustomed to that kind of thinking, there are more sensible approaches to the problem.

I would recommend implementing a merge sort:

Break list into two sub-lists, 
either by counting off half the elements into one sublist 
  and the rest in the other,
or by copying every other element from the original list 
  into either of the new lists.

Sort each of the two smaller lists (recursion here, obviously).

Assemble a new list by selecting the smaller from the front of either sub-list
until you've exhausted both sub-lists.

The recursion is in the middle of that, and I don't see a clever way of making the algorithm tail recursive. Still, I think it's O(log-2) in time and also doesn't place an exorbitant load on the stack.

Have fun, good luck!

Answer 6

Even though, when coding Scala, I'm used to prefer functional programming style (via combinators or recursion) over imperative style (via variables and iterations), THIS TIME, for this specific problem, old school imperative nested loops result in simpler and more performant code.

I don't think falling back to imperative style is a mistake for certain classes of problems, such as sorting algorithms which usually transform the input buffer in place rather than resulting to a new collection.

My solution is:

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}


class SelectionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for (i <- 0 until buffer.length) {
      var min = i
      for (j <- i until buffer.length) {
        if (buffer(j) < buffer(min))
          min = j
       }
       swap(buffer, i, min)
     }
  }
}

As you can see, to achieve parametric polymorphism, rather than using java.lang.Comparable, I preferred scala.math.Ordered and Scala View Bounds rather than Upper Bounds. That's certainly works thanks to Scala Implicit Conversions of primitive types to Rich Wrappers.

You can write a client program as follows:

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))

Answer 7

A simple functional program for selection-sort in Scala

def selectionSort(list:List[Int]):List[Int] = {
  @tailrec
  def selectSortHelper(list:List[Int], accumList:List[Int] = List[Int]()): List[Int] = {

    list match {
      case Nil => accumList
      case _ => {
        val min  = list.min
        val requiredList = list.filter(_ != min)
        selectSortHelper(requiredList, accumList ::: List.fill(list.length - requiredList.length)(min))
      }
    }
  }
  selectSortHelper(list)
}

Answer 8

Thanks for the hints above, they were very inspiring. Here's another functional approach to the selection sort algorithm. I tried to base it on the following idea: finding a max / min can be done quite easily by min(A)=if A=Nil ->Int.MaxValue else min(A.head, min(A.tail)). The first min is the min of a list, the second the min of two numbers. This is easy to understand, but unfortunately not tail recursive. Using the accumulator method the min definition can be transformed like this, now in correct Scala:

def min(x: Int,y: Int) = if (x<y) x else y

def min(xs: List[Int], accu: Int): Int = xs match {
    case Nil => accu
    case x :: ys => min(ys, min(accu, x))
}

(This is tail recursive)

Now a min version is needed which returns a list leaving out the min value. The following function returns a list whose head is the min value, the tail contains the rest of the original list:

def minl(xs: List[Int]): List[Int] = minl(xs, List(Int.MaxValue))

def minl(xs: List[Int],accu:List[Int]): List[Int] = xs match {
// accu always contains min as head
    case Nil => accu take accu.length-1
    case x :: ys => minl(ys, 
        if (x<accu.head) x::accu else accu.head :: x :: accu.tail )
}

Using this selection sort can be written tail recursively as:

def ssort(xs: List[Int], accu: List[Int]): List[Int] = minl(xs) match {
    case Nil => accu
    case min :: rest => ssort(rest, min::accu)
}

(reverses the order). In a test with 10000 list elements this algorithm is only about 4 times slower than the usual imperative algorithm.

Answer 9

You may want to try replacing your while loops with recursion, so, you have two places where you can create new recursive functions.

That would begin to get rid of some vars.

This was probably the toughest lesson for me, trying to move more toward FP.

I hesitate to show solutions here, as I think it would be better for you to try first.

But, if possible you should be using tail-recursion, to avoid problems with stack overflows (if you are sorting a very, very large list).

Answer 10

Here is my point of view on this problem: SelectionSort.scala

def selectionsort[A <% Ordered[A]](list: List[A]): List[A] = {
  def sort(as: List[A], bs: List[A]): List[A] = as match {
    case h :: t => select(h, t, Nil, bs)
    case Nil => bs
  }

  def select(m: A, as: List[A], zs: List[A], bs: List[A]): List[A] = 
    as match {
      case h :: t => 
        if (m > h) select(m, t, h :: zs, bs)
        else select(h, t, m :: zs, bs)
      case Nil => sort(zs, m :: bs)
    }

  sort(list, Nil)
}

There are two inner functions: sort and select, which represents two loops in original algorithm. The first function sort iterates through the elements and call select for each of them. When the source list is empty it return bs list as result, which is initially Nil. The sort function tries to search for maximum (not minimum, since we build result list in reversive order) element in source list. It suppose that maximum is head by the default and then just replace it with a proper value.

This is 100% functional implementation of Selection Sort in Scala.

Answer 11

Here is my solution

def sort(list: List[Int]): List[Int] = {
    @tailrec
    def pivotCompare(p: Int, l: List[Int], accList: List[Int] = List.empty): List[Int] = {
      l match {
        case Nil              => p +: accList
        case x :: xs if p < x => pivotCompare(p, xs, accList :+ x)
        case x :: xs          => pivotCompare(x, xs, accList :+ p)
      }
    }
    @tailrec
    def loop(list: List[Int], accList: List[Int] = List.empty): List[Int] = {
      list match {
        case x :: xs =>
          pivotCompare(x, xs) match {
            case Nil       => accList
            case h :: tail => loop(tail, accList :+ h)
          }
        case Nil => accList
      }
    }

    loop(list)
  }