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