It has been noted in a few places that the 2 line quicksort demo in the Introduction section of the haskell wiki

http://www.haskell.org/haskellwiki/Introduction

isn't a "real" quicksort, and wouldn't scale well with longer lists. Interested, and wanting to put my recently learned test data generating skills to the test, I put this to the test with a little suite for various versions of quickcheck I found lying around.

My patience extends to <3 minutes for waiting for a result, which for my tests was about the amount needed for a million integer long list. This was definitely faster for the "treesort" below than the naive quicksort from the wiki.

(Prelude sort, which I think is mergesort, just blew the stack.)

I wonder if there are "tricks" or lore that could be applied to get better results or insight.

t.


{-import Control.Monad (when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray
import System.IO.Unsafe
import Control.Monad
-}
import Test.QuickCheck hiding (test)
import System.Random
import Data.List

{-
$ time ghci -e 'test treesort 6' quicksort.hs # a "real" quicksort, according to roconnor
1000000

real        2m18.702s
user        1m3.296s
sys        0m0.453s
$ time ghci -e 'test qs1 6' quicksort.hs # "naive" (from the wiki intro to haskell, not a "real" quicksort
1000000

real        4m18.174s
user        1m57.615s
sys        0m0.665s
$ time ghci -e 'test sort 6' quicksort.hs # mergesort from the prelude
*** Exception: stack overflow

real        0m13.634s
user        0m3.805s
sys        0m0.446s
hartthoma@linuxpt:~/ProjectRepos/learning/quicksort>
-}

-- For interactive development, I wound up working in hugs +S +I,
-- because ghci in emacs tended to lock up
-- hugs just segfaults, but at least the computer doesn't lock.
-- by the way, is there a way to get ghci to behave similarly to hugs? (restricted memory mode?)

-- t1 and t2 are about the same speed for n = 4, got bored of waiting for n great.
-- naive, "not really" quicksort according to recent reddit discussion.

test sortf n = genlist n >>= return . ( length . sortf )  

-- naive
qs1 []     = []
qs1 (x:xs) = qs1 (filter (< x) xs) ++ [x] ++ qs1 (filter (>= x) xs)
 

-- roconnor claims that "real" quicksort in haskell is really treesort.
-- from http://programming.reddit.com/info/2h0j2/comments
--I'm talking about a deforested version of tree sort. In tree sort you build a binary search tree by adding the head of the list to the root of the tree, and then building binary search trees for those items less than the root, and those items greater than the root.
qs2 l = treeSort l
treeSort l = foldTree (\x lft rht -> lft++[x]++rht) [] (mkTree l)

-- After building the search tree, it is turned into a list by folding \x lft rht -> lft++[x]++rht.
foldTree f g Leaf = g
foldTree f g (Node x l r) = f x (foldTree f g l) (foldTree f g r)

mkTree [] = Leaf
mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs))

-- If you deforest this algorithm (removing the intermediate tree structure) you are left with
-- treeSort' [] = []
-- treeSort' (x:xs) = treeSort' (filter (<= x) xs) ++ [x] ++ treeSort' (filter (x <) xs)


-- for testing
genlist n = rgen ( vector $ 10^n ) :: IO [Int]
rgenIntList = rgen (arbitrary :: Gen [Int]) :: IO [Int]
rgen gen = do sg <- newStdGen
              return $ generate 10000 sg gen

data Tree a = Leaf | Node a (Tree a) (Tree a)

---

This e-mail may contain confidential and/or privileged information. If you
are not the intended recipient (or have received this e-mail in error)
please notify the sender immediately and destroy this e-mail. Any
unauthorized copying, disclosure or distribution of the material in this
e-mail is strictly forbidden.