(Error in quickSort)
Revision as of 13:48, 19 May 2008
The quicksort quoted in Introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does.
Here are some points to how the "real" quicksort would look in haskell.
Lennart Augustsson has a quicksort entry on his blog which is pure (no unsafe):
Another version (uses System.IO.Unsafe), is below.
There is also a "parallel" quicksort at
roconnor claims that in haskell the "real" quicksort is really a treesort:
Unfortunately none of the above "real" quicksorts seems to compile as given, when copy/pasted into ghci. Can someone fix? The "parallel" quicksort gave error "unknown package concurrent" when I ran make in quicksort/gransim.
Has anyone got a functioning "real" quicksort that works on copy/paste?
import Control.Monad (when) import Control.Monad.ST import Data.Array.ST import Data.Array.IArray import Data.Array.MArray qsort :: (IArray a e, Ix i, Enum i, Ord e) => a i e -> a i e qsort arr = processArray quickSort arr processArray :: (IArray a e, IArray b e, Ix i) => (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e processArray f (arr :: a i e) = runST $ do arr' <- thaw arr :: ST s (STArray s i e) f arr' unsafeFreeze arr' quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m () quickSort arr = do (lo, hi) <- getBounds arr qsort' lo hi where qsort' lo hi | lo >= hi = return () | otherwise = do p <- readArray arr hi l <- mainLoop p lo hi swap l hi qsort' lo (pred l) qsort' (succ l) hi mainLoop p l h | l >= h = return l | otherwise = do l' <- doTil (\l' b -> l' < h && b <= p) succ l h' <- doTil (\h' b -> h' > l' && b >= p) pred h when (l' < h') $ swap l' h' mainLoop p l' h' doTil p op ix = do b <- readArray arr ix if p ix b then doTil p op (op ix) else return ix swap xi yi = do x <- readArray arr xi readArray arr yi >>= writeArray arr xi writeArray arr yi x
This uses various extensions to make the types ridiculously general, but the actual algorithm (quickSort) is plain Haskell.