add quicksort
authorSimon Marlow <marlowsd@gmail.com>
Mon, 21 Dec 2009 12:09:22 +0000 (12:09 +0000)
committerSimon Marlow <marlowsd@gmail.com>
Mon, 21 Dec 2009 12:09:22 +0000 (12:09 +0000)
parallel/quicksort/QuickSort.hs [new file with mode: 0644]
parallel/quicksort/QuickSortD.hs [new file with mode: 0644]

diff --git a/parallel/quicksort/QuickSort.hs b/parallel/quicksort/QuickSort.hs
new file mode 100644 (file)
index 0000000..2b78ada
--- /dev/null
@@ -0,0 +1,48 @@
+{-# LANGUAGE BangPatterns #-}\r
+-------------------------------------------------------------------------------\r
+--- $Id: QuickSortD.hs#3 2008/05/27 18:27:02 REDMOND\\satnams $\r
+-------------------------------------------------------------------------------\r
+\r
+module Main\r
+where\r
+import System.Time\r
+import System.Random\r
+import Control.Parallel\r
+import Data.List\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+quicksortD :: Int -> Int -> [Int] -> [Int]\r
+quicksortD _ _ [] = []\r
+quicksortD _ _ [x] = [x]\r
+quicksortD !currentDepth !limit xs | currentDepth >= limit = sort xs\r
+quicksortD !currentDepth !limit (x:xs)\r
+  = hisort `par` forceList r `pseq` r \r
+    where\r
+    r = losort ++ x:hisort\r
+    losort = quicksortD (currentDepth+1) limit [y | y <- xs, y < x]\r
+    hisort = quicksortD (currentDepth+1) limit [y | y <- xs, y >= x]\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+forceList :: [a] -> ()\r
+forceList [] = ()\r
+forceList (x:xs) = x `pseq` forceList xs\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+size :: Int\r
+size = 500000\r
+\r
+depth :: Int\r
+depth = 8\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+main :: IO ()\r
+main\r
+  = do putStrLn ("QuickSortD size=" ++ show size ++ " depth=" ++ show depth)\r
+       let input = (take size (randomRs (0, 100000) (mkStdGen 42)))::[Int]\r
+       let r = quicksortD 0 depth input\r
+       pseq r (return ())\r
+       putStrLn ("Sum of sort: " ++ show (sum r))\r
diff --git a/parallel/quicksort/QuickSortD.hs b/parallel/quicksort/QuickSortD.hs
new file mode 100644 (file)
index 0000000..33f1f4f
--- /dev/null
@@ -0,0 +1,48 @@
+-------------------------------------------------------------------------------\r
+--- $Id: QuickSortD.hs#3 2008/05/27 18:27:02 REDMOND\\satnams $\r
+-------------------------------------------------------------------------------\r
+\r
+module Main\r
+where\r
+import System.Time\r
+import System.Random\r
+import Control.Parallel\r
+import Data.List\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+quicksortD :: Ord a => Int -> Int -> [a] -> [a]\r
+quicksortD _ _ [] = []\r
+quicksortD _ _ [x] = [x]\r
+quicksortD currentDepth limit xs | currentDepth >= limit = sort xs\r
+quicksortD currentDepth limit (x:xs)\r
+  = (forceList losort) `par`\r
+    (forceList hisort) `pseq`\r
+    losort ++ (x:hisort)\r
+    where\r
+    losort = quicksortD (currentDepth+1) limit [y | y <- xs, y < x]\r
+    hisort = quicksortD (currentDepth+1) limit [y | y <- xs, y >= x]\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+forceList :: [a] -> ()\r
+forceList [] = ()\r
+forceList (x:xs) = x `pseq` forceList xs\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+size :: Int\r
+size = 1000000\r
+\r
+depth :: Int\r
+depth = 3\r
+\r
+-------------------------------------------------------------------------------\r
+\r
+main :: IO ()\r
+main\r
+  = do putStrLn ("QuickSortD size=" ++ show size ++ " depth=" ++ show depth)\r
+       let input = (take size (randomRs (0, 100000) (mkStdGen 42)))::[Integer]\r
+       let r = quicksortD 0 depth input\r
+       pseq r (return ())\r
+       putStrLn ("Sum of sort: " ++ show (sum r))\r