Lytol - 1 month ago 16
Scala Question

# Selection sort in functional Scala

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

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] =
(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
}
``````

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(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
``````
Source (Stackoverflow)