## Monday, August 20, 2007

Quicksort in Haskell Quicksort is a commonly used example of how succinct Haskell programming can be. It usually looks something likes this:
```qsort :: (Ord a Bool) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)
```
The problem with this function is that it's not really Quicksort. Viewed through sufficently blurry glasses (or high abstraction altitude) it's looks like the real Quicksort. What they have in common is overall algorithm: pick a pivot (always the first element), then recursively sort the ones that are smaller, the ones that are bigger, and then stick it all together. But in my opinion the real Quicksort has to be imperative because it relies on destructive update; and it uses a very elegant partitioning algorithm. The partitioning works like this: scan from the left for an element bigger than the pivot, then scan from the right for an element smaller than the pivot, and then swap them. Repeat this until the array has been partitioned. Haskell has a variety of array types with destructive updates (in different monads), so it's perfectly possible to write the imperative Quicksort in Haskell. To make the code look reasonably nice I'm going to use my C-like DSEL to write the code. Here it is:
```qsortM :: forall i a m r arr .
(MonadRef m r, Num i, Ix i, MArray arr a m, Ord a Bool) =>
arr i a -> m (arr i a)
qsortM ma = runE \$ do
(lb, ub) <- embed \$ getBounds ma
let mlb = pure0 lb
mub = pure0 ub
a <- liftArray ma

let qsort' l r =
if1 (r > l) \$ do
i <- auto l
j <- auto (r+1)
let v = a[l] :: E m a
iLTj = i < (j :: E m i)
while iLTj \$ do
while ((i += 1) < mub && a[i] < v)
skip
while (a[j -= 1] > v)
skip
if1 iLTj \$ do
a[i] =:= a[j]
a[l] =:= a[j]
qsort' l (j-1)
qsort' i r

qsort' mlb mub
return ma
```
```qsortA :: forall i a . (Num i, Ix i, Ord a Bool) => Array i a -> Array i a
qsortA a = runSTArray sa
where sa :: ST s (STArray s i a)
sa = thaw a >>= qsortM
```
We're using runSTArray instead of runST, because it provides an efficient way to turn a mutable array on the inside into an immutable array on the outside. The thaw function turns an immutable array into a mutable one, but it has to make a copy to be safe, since we don't want to mutate the original. Finally, if we want to sort lists we can always convert back and forth.
```asList :: (Array Int a -> Array Int a) -> ([a] -> [a])
asList f xs = elems . f . listArray (1, length xs) \$ xs

qsort :: (Prelude.Ord a) => [a] -> [a]
qsort = asList qsortA
```
The final qsort has the normal type signature (I switched to the normal Ord again).

Labels:

Paul Johnson said...

Interesting. I've sometimes thought of doing a shuffle function like this, since O(n) shuffling as described by Knuth also needs a constant time swap item operation. Oleg has described a functional shuffle algorithm, but its O(n * log n)

On the other hand I wonder if you couldn't do swapping in some wierd zipper structure. I'll think about it.

Tuesday, August 21, 2007 at 11:30:00 PM GMT+1
jsnx said...

Monday, October 15, 2007 at 9:14:00 PM GMT+1
namekuseijin said...

I thought the whole point of using high level languages was to favor and focus on higher level abstractions and get away from low level details and mechanics. You've just brought it all into your version: state, lots of verbose low-level machinery and imperative thinkage...

look: if you want C, you know where to get it. Let's not fill Haskell code with lots of monads and verbosity just for the sake of it, right?

Wednesday, November 7, 2007 at 3:10:00 AM GMT
GameOn said...

namekuseijin: Whilst I appreciate what you're saying I firmly believe that if you can save such a large amount of memory, do so.

paul johnson: thanks for the tip about an O(n) shuffle, I'll have a look at it.

Blog Author: Thanks for such an informative article on the 'proper' quicksort.

Friday, November 30, 2007 at 1:11:00 AM GMT
Parch said...

Thanks for posting this code. Only yesterday I was wondering what quicksort in an 'elegant' language (e.g. lisp) would look like. I tried it, and quickly realized making things as efficient as C wasn't so simple. I remembered that Haskell had the 'shortest' quicksort definition of nearly any language, then wondered what an efficient haskell version would look like... and now thanks to haskellwiki, here I am. :)

Sunday, June 22, 2008 at 5:49:00 AM GMT+1

Indonesia Siap Bersaing di SERP | Rumah Mungil Yang Sehat

Friday, December 17, 2010 at 7:29:00 PM GMT
Paul Ceccato said...

So, it's certainly more verbose, and uglier. But how much faster is this code than the elegant version?

Thursday, March 8, 2012 at 4:18:00 AM GMT
Enrique Santos Leal said...

The problem is not functional vs. imperative. The extra time of the "elegant" solution is because 'filter' is called twice with the same argument on each recursion, so that total time is much more than twice the neccessary.
The solution to keep it elegant and short is to use a modified version of filter who return both, the filtered list and the rest of the list, in order to call it once:

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort ls ++ [x] ++ qsort gs
where (ls, gs) = splitFilter (< x) xs

splitFilter :: (a -> Bool) -> [a] -> ([a], [a])
splitFilter p xs = sep xs [] [] where
sep [] ps qs = (ps, qs)
sep (o:os) ps qs
| p o = sep os (o:ps) qs
| otherwise = sep os ps (o:qs)

Sunday, February 10, 2013 at 12:38:00 PM GMT
augustss said...

Enrique, I'm aware of how to make functional quicksort faster. If you take a look at Data.List you can find a qsort (and a merge sort) originally written by me.

I stand by my original post; if you don't do the clever in-place partitioning I don't really think it's quicksort.

Monday, February 18, 2013 at 5:30:00 PM GMT
Enrique Santos said...

Ok, augustss, I agree, sorry. Your point of view is good, as well as your article and your programming work.
"This implementation has very poor runtime and space complexity, but that can be improved, at the expense of some of the elegance."
It is true, of course, but it makes people who try Haskell to think that it is not a serious language, just a beautiful academic one. The same idea is expressed in Haskellwiki Introduction:
"the Haskell program allocates quite a lot of extra memory behind the scenes, and runs rather slower than the C program."
My point is that there are better implementations of quicksort in Haskell (ok, not true quicksort) between the typical simple one and the long and difficult to read like yours. So, it is not a criticism to you, but to the introduction texts which trying to show Haskell so simple and elegant makes new people to get out of it.
I am not Haskell expert (that is why I read introduction texts). I noticed later that there is the function 'partition' on Data.List that makes the same as my 'splitFilter'. If we substitute the slow (++) operator with (:) in the second place we gain a bit more. Or better we could use Data.Sequence instead of Data.List, improving efficiency with very low loss in elegance, simplicity and readability. So, introduction texts are comparing a bad quicksort implementation in functional programming with the best in imperative programming. That is my criticism.
Your proposal is very interesting for experts, Haskell with monads provides a cleaner way to do destructive updates than C or other imperative languages.

Monday, February 18, 2013 at 7:59:00 PM GMT
Heemanshu Bhalla said...

Nice tutorial sir,

I have taken reference from this link below
Its easy to understand
Algorithm and Implementation Program of Quick Sort
http://geeksprogrammings.blogspot.com/2014/02/algorithm-quick-sort-program.html﻿

Saturday, February 22, 2014 at 7:23:00 PM GMT
Jeffrey Seyfried said...

You can also write an in place quicksort without using a dsl:

qSort :: (Ord e, MArray a e m) => a Int e -> m ()
qSort = liftM2 (>>=) getBounds qSortSlice
where qSortSlice a (k, l) = when (k < l) \$
readArray a k >>= \pivot -> nextToSwap a pivot (k, l) >>=
((liftM2 (>>) (swap a) (nextToSwap a pivot)) `untilM` (return . uncurry (>=))) >>= \(i, j) ->
qSortSlice a (k, j-1) >> qSortSlice a (i+1, l)
nextToSwap a pivot (i, j) = liftM2 (,)
((return . ( 1 +)) `untilM` (liftM (>= pivot) . readArray a) \$ i)
((return . (-1 +)) `untilM` (liftM (<= pivot) . readArray a) \$ j)
swap a (i, j) = readArray a i >>= \t -> readArray a j >>= writeArray a i >> writeArray a j t
untilM f c i = c i >>= \b -> if b then return i else f i >>= f `untilM` c

Thursday, February 27, 2014 at 6:20:00 AM GMT