The quicksort algorithm in Haskell

Question

I am learning Haskell programming language mainly from this source. And there I have encouraged with "an elegant" realization of the quicksort sorting algorithm (the Quick, sort! section). Here it is:

Book's implementation

quicksort :: ( Ord a ) = > [ a ] -> [ a ]
quicksort [] = []
quicksort ( x : xs ) =
 let smallerSorted = quicksort [ a | a <- xs , a <= x ]
 biggerSorted = quicksort [ a | a <- xs , a > x ]
 in smallerSorted ++ [ x ] ++ biggerSorted

The problem with this implementation (as I think) is doubled number of comparisons inside the let binding every time. Isn't the fact that those of a's that already in the smallerSorted list cannot be in the biggerSorted list, so we don't need to compare x with them anymore.

In order to "improve" the above approach I have written my own implementation, where I use auxiliary local function split that splits a list into two parts: less than (or equal to) x and greater than x.

My implementation

quick_sort :: (Ord a) => [a] -> [a]
quick_sort [] = [] --edge condition 
quick_sort (x : xs) = --general condition
 let (lt, gt) = split x xs
 in (quick_sort lt) ++ [x] ++ (quick_sort gt) 
 where
 --split function is used to split a list
 --into two sublists: one for elements
 --less or equal (lt) than some value - x
 --and one for those that greater (gt) than x
 --NOTE: split function is also recursive
 split x [] = ([], []) --edge condition
 split x (h : hs) --general condition
 | h <= x =
 let (lt, gt) = split x hs
 in ( (h : lt), gt )
 | otherwise =
 let (lt, gt) = split x hs
 in ( lt, (h : gt) )

P.S. For a while I am not able to compare two approaches, but on the worst cases (when list to sort is already sorted) it seems that my implementation is a bit slower.

• cole: You are right about the unnecessary computations (and the helper function you wrote is probably similar to one in Data.List, I think it’s maybe called partition). However, there’s a subtler "problem" with the efficiency of this implementation, which you can read about here. There’s a paper linked in one of the answers about the sieve of Eratosthenes that is also worth a read if you’re interested in learning about some subtleties of efficiency in haskell.

Answer 1

First of all, great that you used type annotations, as they're sometimes missing. However, there are some remarks:

• "edge" and "general"` condition are usually called "base case" and "recursive case"
• "base case" and "recursive case" aren't commented in Haskell code, as they are everywhere
• split is generic enough to be defined at top-level
• split has a little bit of duplication that we can remove with a single where clause
• functions are usually named in camelCase instead of snake_case, so we'd call it quickSort.

If we apply that we end up with

quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x : xs) =
 let (lt, gt) = split x xs
 in (quickSort lt) ++ [x] ++ (quickSort gt) 
split :: (Ord a) => a -> [a] -> ([a], [a])
split x [] = ([], [])
split x (h : hs)
 | h <= x = ( h : lt, gt)
 | otherwise = ( lt, h : gt)
 where
 (lt, gt) = split x hs

That being said, split seems so helpful that there should be some function already in the standard library. And it turns out there is, namely partition :: (a -> Bool) -> [a] -> ([a],[a]) from Data.List:

split :: (Ord a) => a -> [a] -> ([a], [a])
split x = partition (<= x)

That's a lot cleaner than our own implementation. So how do we find partition if we don't know about it yet? We use Hoogle . However, a query for Ord a => a -> [a] -> ([a],[a]) does not yield partition. It's sometimes a good idea to generalize the query a little bit, for example to [a] -> ([a],[a]), as Hoogle also scans parts of the type signature. That way, we find partition.

If we're going for brevity, we can then inline split to gain

-- | Sorts the given list in an ascending order.
quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x : xs) =
 let (lt, gt) = partition (<= x) xs
 in (quickSort lt) ++ [x] ++ (quickSort gt)

but that's up to personal preference, as the compiler will inline split anyway.