Introduction/Direct Translation
Jump to navigation
Jump to search
This code seems to have been created because the quicksort quoted in the introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does. To be fair, this is how the "real" quicksort would look in haskell.
Lennart Augustsson has a quicksort entry on his blog which is pure (no unsafe):
http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html
Another version (uses System.IO.Unsafe):
import Control.Monad (when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray
import System.IO.Unsafe
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 = case bounds arr of (lo,hi) -> 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 pred op ix = do
b <- readArray arr ix
if pred ix b then doTil pred 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.