1 
    2 
    3 
    4 
    5 
    6 
    7 
    8 
    9 
   10 
   11 
   12 
   13 module Sort(insertSort,mergeSort,quickSort,lazySort)  where
   14 
   15 
   16 
   17 
   18 
   19 
   20 
   21 insertSort::(Ord a) => [a] -> [a]
   22 insertSort xs = foldr insertion [] xs
   23 
   24 insertion :: (Ord a) => a -> [a] -> [a]
   25 insertion x [] = [x]
   26 insertion x (y:ys) 
   27         | x <= y    = x:y:ys
   28         | otherwise = y:insertion x ys
   29 
   30 
   31 
   32 
   33 
   34 
   35 
   36 mergeSort :: (Ord a) => [a] -> [a]
   37 mergeSort xs
   38         = if (n <=1 ) then xs 
   39           else 
   40              (mergeList 
   41                 ( mergeSort (take (n `div` 2) xs))
   42                 ( mergeSort (drop (n `div` 2) xs)))
   43           where
   44                 n = length xs
   45 
   46 mergeList :: (Ord a) => [a] -> [a] -> [a]
   47 mergeList []   ys = ys
   48 mergeList xs   [] = xs
   49 mergeList (x:xs) (y:ys)
   50         | x <= y    = x:mergeList xs (y:ys)
   51         | otherwise = y:mergeList (x:xs) ys
   52 
   53 
   54 
   55 
   56 
   57 quickSort :: (Ord a) => [a] -> [a]
   58 quickSort []     = []
   59 quickSort (x:xs) = (quickSort [y | y<-xs, y<x]) ++ [x] ++ 
   60                    (quickSort [y | y<-xs, y>=x])
   61 
   62 
   63 
   64 
   65 
   66 
   67 
   68 
   69 
   70 
   71 
   72 
   73 
   74 
   75 
   76 lazySortLe :: (a -> a -> Bool) -> [a] -> [a]
   77 lazySortLe le l = lazyQsort le   l []
   78 
   79 lazySort :: (Ord a) => [a] -> [a]
   80 lazySort      l = lazyQsort (<=) l []
   81 
   82 -- lazyQsort is stable and does not concatenate.
   83 lazyQsort :: (a -> a -> Bool) -> [a] -> [a] -> [a]
   84 lazyQsort le []     r = r
   85 lazyQsort le [x]    r = x:r
   86 lazyQsort le (x:xs) r = qpart le x xs [] [] r
   87 
   88 -- rlazyQsort is as lazyQsort but anti-stable, 
   89 -- i.e. reverses equal elements.
   90 rlazyQsort :: (a -> a -> Bool) -> [a] -> [a] -> [a]
   91 rlazyQsort  le []     r = r
   92 rlazyQsort le [x]    r = x:r
   93 rlazyQsort  le (x:xs) r = rqpart le x xs [] [] r
   94 
   95 -- qpart partitions and sorts the sublists
   96 -- rlt and rge are in reverse order and must be sorted with an
   97 -- anti-stable sorting
   98 qpart :: (a -> a -> Bool) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
   99 qpart le x [] rlt rge r =
  100     rlazyQsort le rlt (x:rlazyQsort le rge r)
  101 qpart le x (y:ys) rlt rge r =
  102     if le x y then
  103         qpart le x ys rlt (y:rge) r
  104     else
  105         qpart le x ys (y:rlt) rge r
  106 
  107 rqpart :: (a -> a -> Bool) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
  108 rqpart le x [] rle rgt r =
  109     lazyQsort le rle (x:lazyQsort le rgt r)
  110 rqpart le x (y:ys) rle rgt r =
  111     if le y x then
  112         rqpart le x ys (y:rle) rgt r
  113     else
  114         rqpart le x ys rle (y:rgt) r
  115 
  116 
  117 
  118 
  119 
  120 
  121 
  122 
  123 
  124 
  125 
  126 
  127 
  128 
  129 
  130 
  131 
  132 randomInts :: Int -> Int -> [Int]
  133 randomInts s1 s2 =
  134     if 1 <= s1 && s1 <= 2147483562 then
  135         if 1 <= s2 && s2 <= 2147483398 then
  136             rands s1 s2
  137         else
  138             error "randomInts: Bad second seed."
  139     else
  140         error "randomInts: Bad first seed."
  141 
  142 rands :: Int -> Int -> [Int]
  143 rands s1 s2 
  144    = if z < 1 then z + 2147483562 : rands s1'' s2'' 
  145      else 
  146          z : rands s1'' s2''
  147      where        
  148         k    = s1 `div` 53668
  149         s1'  = 40014 * (s1 - k * 53668) - k * 12211
  150         s1'' = if s1' < 0 then s1' + 2147483563 else s1'
  151     
  152         k'   = s2 `div` 52774
  153         s2'  = 40692 * (s2 - k' * 52774) - k' * 3791
  154         s2'' = if s2' < 0 then s2' + 2147483399 else s2'
  155 
  156         z    = s1'' - s2''
  157 
  158 
  159 
  160 
  161 
  162 
  163 
  164 
  165 randomDoubles :: Int -> Int -> [Double]
  166 randomDoubles s1 s2 = map (\x -> (fromIntegral x * 4.6566130638969828e-10))
  167                           (randomInts s1 s2)
  168 
  169 
  170 
  171 
  172 
  173 test1,test2,test3,test4,test5,test6,test7::[Int]
  174 test1 = [1..10]
  175 test2 = [10,9..1]
  176 test3 = [1..500]
  177 test4 = [500,499..1]
  178 
  179 test5 = take 10   (randomInts 123213 342234)
  180 test6 = take 100  (randomInts 123213 342234)
  181 test7 = take 1000 (randomInts 123213 342234)
  182 
  183 
  184 
  185 
  186 
  187 
  188 
  189 
  190 
  191 
  192 
  193 
  194 
  195 
  196 
  197 
  198 
  199 
  200 
  201 
  202 
  203 
  204 
  205 
  206 
  207 
  208 
  209 
  210 
  211 
  212 
  213 
  214 
  215 
  216 
  217 
  218 
  219 
  220 
  221 
  222 
  223 
  224 
  225 
  226 
  227 
  228 
  229 
  230 
  231 
  232 
  233 
  234 
  235 
  236 
  237 
  238 
  239