Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- {-# LANGUAGE ScopedTypeVariables #-}
- module QuickSort where
- import Control.Monad
- import Control.Monad.Primitive
- import Data.List
- import qualified Data.Vector as V
- import qualified Data.Vector.Mutable as MV
- import Data.Vector.Unboxed hiding (filter, forM_, head,
- reverse, tail, (++))
- import qualified Data.Vector.Unboxed.Mutable as M
- import Test.QuickCheck
- import Test.QuickCheck.Instances
- qs :: Ord a => [a] -> [a]
- qs [] = []
- qs (x:xs) = qs left ++ [x] ++ qs right
- where
- left = filter (<x) xs
- right = filter (>=x) xs
- quickSort :: Vector Int -> Vector Int
- quickSort = modify f
- where
- f :: (Ord a, PrimMonad m, Unbox a) => MVector (PrimState m) a -> m ()
- f v = qsort v 0 (M.length v - 1)
- where
- qsort a low high =
- when (low < high) $ do
- p <- partition a low high
- qsort a low (p - 1)
- qsort a (p + 1) high
- partition a low high = do
- pivot <- M.read a high
- go low (high-1) low pivot a
- go l h i pivot a =
- if l <= h
- then do
- aj <- M.read a l
- if aj <= pivot
- then do
- M.swap a l i
- go (l+1) h (i+1) pivot a
- else
- go (l+1) h i pivot a
- else do
- M.swap a (h+1) i
- return i
- test = quickCheck $ \(v :: Vector Int) ->
- (quickSort v) == (fromList $ sort (toList v))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement