Authored by Win Myo Htet

The previous post has been about doing Scala exercise from the Haskell example. Thus, the code is already written in the functional programming paradigm and I have just translated it into Scala language. To learn Scala and functional programming, we have to learn to think in the functional programming way. How do we do that? As usual, there is no easy way. We can only learn through getting our hands dirty by exercising through thinking in functional programming way.

So, Quicksort has been picked for this exercise and the Quicksort wiki will be used as a common reference. I will start implementing Quicksort in Scala by following the pseudo code described under the sub title "In-Place version". The Wiki has talked about some methods of choosing the pivot. However, it is not trivial to choose the pivot and it all depends on the set of data for the pivot-chooising-method to be meaningful. So, we will just pick the value of the first index of the array. Remember, the first value of the array can still be any value. So, here they are, very Java like.

Partition method:

def partition(left : Int, right : Int, pivotIndex : Int, array : Array[Int]) : Int = { val pivotValue = array(pivotIndex) array(pivotIndex) = array(right) array(right) = pivotValue var storeIndex = left for (i <- left until right) { if (array(i) <= pivotValue) { val temp = array(i) array(i) = array(storeIndex) array(storeIndex) = temp storeIndex = storeIndex + 1 } } val temp2 = array(storeIndex) array(storeIndex) = array(right) array(right) = temp2 storeIndex }

quickSort method

def quickSort(left : Int, right : Int, array : Array[Int], direction : String = "begin") : Unit = { if (left < right) { val pivotIndex = 0 val newPivotIndex = partition(left, right, pivotIndex, array) quickSort(left, newPivotIndex - 1, array, "left") quickSort(newPivotIndex + 1, right, array, "right") } }

The codes are simply the implementation of the pseudo code. The only thing that differ from pseudo code might be that I have used the Scala's default argument variable for "direction" for debugging purpose.

To be honest, I don't quite know how to re-implement this code into functional programming way. So, I have to get back to the basic abstract under sub title, "Algorithm".

1. pick a pivot(done!)

2. put a lesser value on the left, greater value on the right, put pivot where it belongs, which is between lesser and greater, of course.

3. do the same process for lesser and greater by way of recursion.

So how do we do step No. 2. Well, first, let's pick

*List*as the data structure for our method since

*List*is the preferred data structure when it comes to functional programming. The input will be

*List*. Then, there are

*lesser*and

*greater*created based on the condition that the value of element of the List lesser(<) than pivot go to

*lesser*List and the value of element of the List greater(>) than pivot go to

*greater*List. How do we do that? We have to feed our variable

*List*into some looping mechanism that will give us back two

*List*s.

From my experience with Oleg's Tic Tac Toe code. He makes use of

*foldLeft*quite a lot. So,

*folding*might be a solution? Yes, it is. If you read that blog on my understanding of the

*folding*process, you will see that we can feed any collection into

*folding*and can process the data for all kind of type of data as an end result. If you want to know how I come into this conclusion along with the thinking process, you need to read through that Tic Tac Toe blogs series.

So, folding will be the looping mechanism. I have understood the

*folding*process to involve

**. The**

*(foldLeftSeedValue,foldLeftElement)**will be our end result and we want it to be two*

**foldLeftSeedValue***List*s namely:

*lesser*and

*greater*. So, the seed value has to be a tuple of two

*List*s :

*lesser*and

*greater*. Then, we will do the matching on the conditions :

*lesser*value will be added to the left

*List*and

*greater*value will be added to the right

*List*. If you can visualize this far, that's good enough and let's look at the code.

def myQuickSort(list : List[Int]) : List[Int] = { def myQuickSort(list : List[Int], direction : String = "begin") : List[Int] = { if (list.length <= 1) return list; val pivot = list(0) val pl = list.foldLeft(List[Int](), List[Int]()) { case ((l, r), e) if e < pivot => (e :: l, r) case ((l, r), e) if e > pivot => (l, e :: r) case ((l, r), e) if e == pivot => (l :+ e, r) case ((l, r), e) => println("Error processing : " + e); sys.exit() } myQuickSort(pl._1.slice(0, pl._1.length - 1), "left") ++ List(pivot) ++ myQuickSort(pl._2, "right") } myQuickSort(list) }

I have used nested method, which is not necessary, here. Let's get back to our

*foldLeft*and

*case*condition here. The first

*case*line start with the form of

**(foldLeftSeedValue,foldLeftElement)***as expected*

*, foldLeftSeedValue*is

*(l,r) tuple.*

*foldLeftElement*is

*e*.

*Then if the condtion expression is met, the*

*foldLeftElement*is added to the head of the

*list l*and the

*(l,r) tuple*is passed on for the next iteration. The same can be said of the second match case. The third match case add the value to the end of the

*list l*. The forth match is added because of the compiler warning that matching is not exhaustive. It makes me smile tho. :)

Now, we have a tuple of two Lists:

*l*being lesser and

*r*being greater(on the right side of the pivot value). So we process the

*lesser*and

*greater*

*List*the same way by means of iteration. We have to subtract one value from the lesser because we have added value equal to pivot at the end of the

*lesser*list including the pivot itself. The pivot value has been put into a List which is placed between lesser and greater. The recursion will be exhausted when the list size is less than or equal 1. You know what's next.

So, that's the end of my Quicksort in functional programming way in my own style(TM). However, you cannot count on me to write a truly efficient and fp style Quicksort because I am still a noob! Let's see how Quicksort is coded in Haskell land.

```
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
```

Wow! Much way simpler! If it were not for Alan J. Perlis's wisdom: "

*Simplicity does not precede complexity, but follows it.*", I would have shot myself! Let's look into this Haskell quicksort code. The detail analysis of this code can be found here at section 3.1. The first line is method signature. The second line said that if the list is empty, return empty list. The third line syntax is a bit tricky. If you don't know that tricky syntax (along with the last line of

*greater = ...*), you will think that there is a bug(I do think tho). If you were like me, you would have deduced that

*p*is pivot. Good.

*xs*is an input List. Hmm...

If

*xs*were input

*List*, the resulting List size would have increased because in the last line,

*greater*includes values equal to pivot while we are also manually adding pivot in a List in the middle of

*lesser*and

*greater*. Then, what is

*xs*? Trust me, I am not Omniscience nor super genius. I have to ask my buddy! :D So, this Haskell buddy tells me that

*xs*is a tail List and

*p*(pivot) is the first element of the input List. Now, it all makes sense!

Here is the Scala implementation of that QuickSort

def hsQuickSort(list : List[Int], direction : String = "begin") : List[Int] = { if (list.length <= 1) return list val tail = list.tail val pivot = list(0) val lesser = (for { l <- tail if l < pivot } yield l).toList val greater = (for { g <- tail if g >= pivot } yield g).toList hsQuickSort(lesser, "lesser") ++ List(pivot) ++ hsQuickSort(greater, "greater") }

So, this has been my exercise on thinking in functional programming way. My original FP quicksort is not the most optimized nor simple but I can proudly say that it is my original. I would also encourage you to try to make yourself think and code in FP way. In the beginning, the code will be messy and inefficient but don't get discouraged. Jon Bentley, who gives talk on "Three Beautiful QuickSort", has mentioned of going over 11 versions to a piece of code to achieve the utmost simplicity. Cheer!

*Authored by Win Myo Htet*

*UPDATE*MergeSort

def mergeSort(list:List[Int]):List[Int]={ if(list.length<=1) return list val mid=list.length/2 val left=mergeSort(list.slice(0,mid)) val right=mergeSort(list.slice(mid,list.length)) merge(left,right) } def merge(left:List[Int],right:List[Int]):List[Int]={ if(!left.isEmpty && right.isEmpty)return left if(left.isEmpty && !right.isEmpty)return right if(left.isEmpty && right.isEmpty)return List[Int]() if(left(0)<=right(0)) return List(left(0))++merge(left.tail,right) else return List(right(0))++merge(left,right.tail) }

Haskell MergeSort

```
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x <= y
then x : merge xs (y:ys)
else y : merge (x:xs) ys
mergesort [] = []
mergesort [x] = [x]
mergesort xs = let (as, bs) = splitAt (length xs `quot` 2) xs
in merge (mergesort as) (mergesort bs)
```

Authored by Win Myo Htet

I think Scala can do the same like Haskel for quick sort too

ReplyDeletedef quickSort(list:List[Int]):List[Int] = list match {

case Nil => Nil

case pivot::rest => quickSort(rest.filter(_pivot))

}

Thanks Yi.

ReplyDelete