Is it possible to execute a quicksort list with only one pass?

Question

I am studying haskell, and the function definition that I see is:

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more) where less = filter (< x) xs equal = filter (== x) xs more = filter (> x) xs 

Is it possible to write it with only one workaround, instead of 3?

Answer 1

Late, here is a version that should not leak through space the same way (and seems to work about twice as fast as the other tripartite version here):

 qsort3 xs = go xs [] where go (x:xs) zs = part x xs zs [] [] [] go [] zs = zs part x [] zs abc = go a ((x : b) ++ go c zs) part x (y:ys) zs abc = case compare yx of LT -> part x ys zs (y:a) bc EQ -> part x ys zs a (y:b) c GT -> part x ys zs ab (y:c) 

This concerns a possible problem with using tuples, where let (a,b) = ... actually translated into let t= ...; a=fst t; b=snd t let t= ...; a=fst t; b=snd t let t= ...; a=fst t; b=snd t , which leads to a situation where even after a been consumed and processed, it is still supported around the living, as part of the tuple t , for b to be read from it - although, of course, it is completely unnecessary. This is called the Wadler pair leak problem. Or maybe GHC (with -O2 ) is smarter than that. :)

It also apparently uses a difference list approach (thanks, hammar), which also makes it more efficient (about twice as fast as the version using tuples). I think that part uses the parameters of the battery, as it builds them in the reverse order.

Answer 2

Do you mean something like this?

 quicksort [] = [] quicksort (x:xs) = quicksort less ++ (x : equal) ++ quicksort more where (less, equal, more) = partition3 x xs partition3 _ [] = ([], [], []) partition3 x (y:ys) = case compare yx of LT -> (y:less, equal, more) EQ -> (less, y:equal, more) GT -> (less, equal, y:more) where (less, equal, more) = partition3 x ys 

Please note that this is not a very quick sort, since the real quick sort is in place.

Answer 3

This does not seem to improve anything, but:

 qs (x:xs) = let (a,b) = partition (< x) xs in (qs a) ++ [x] ++ (qs b)