# The Quicksorts

### 20 July, 2013 - 2 min read

I've been spending some time trying to learn Scala and functional programming lately. To do so, I've been following Erik Meijer's lecture series on the subject. It uses Haskell as the example, which makes sense, but I thought it would be a good opportunity to translate the ideas into Scala.

# Quicksorts

In the first lecture Erik mentions quicksort in order to convey a few ideas in functional programming. So I translated it into Scala.

```def quicksort(my_list: Iterable[Int]): Iterable[Int] = my_list match {
case Nil => Nil
case x :: xs => {
quicksort(my_list.filter(_ < x)) ++ Iterable(x) ++
quicksort(my_list.filter(_ > x))
}
}

val r = quicksort(List(10, 100, 1000, 9, 99, 999))
val t = quicksort(Seq(10, 100, 1000, 9, 99, 999))

println(r)
println(t)
```

A few points (and since I'm still learning, these may not be best practices):

1. Erik mentions pattern matching as an important tool in functional programming. Here `case` acts as pattern matching, with two outcomes. Either A) the incoming variable is `Nil`, therefore we should return `Nil`... this covers the empty list case, or B) we have a list and we need to sort it. In this case, `x::xs` acts as a sort of unpacking (I work a lot in python) to give the `head` of the list and the `tail` of the list.
2. The `.filter` operates on a Traversable (I used Iterable, but I think I could have used Traversable) in order to filter out any elements of the list that return false.
3. The line `quicksort(my_list.filter(_ < x)) ++ Iterable(x) ++ quck//omitted` recursively glues together the list from the pivot point `x`. Where x becomes is the head of the list.

Anyways, it's a pretty simple implementation and may not be the best, but I think it makes a log of sense... again showing why Scala is being adopted all over the place.