2009/07/23
■ [Haskell]適当にHaskellをいじる
クイックソートとマージソート
qsort :: [Int] -> [Int] qsort [] = [] qsort (x:xs) = qsort [l | l <- xs, l < x] ++ [x] ++ qsort [l | l <- xs, l >= x] -- merge :: [Int] -> [Int] -> [Int] merge [] [] = [] merge x [] = x merge [] y = y merge (x:xs) (y:ys) = if x >= y then x: merge xs (y:ys) else y: merge (x:xs) ys -- msort :: [Int] -> [Int] msort [] = [] msort [x] = [x] msort l = msort' $ splitAt (div (length l) 2) l where msort' ([a],[b]) = merge [a] [b] msort' ( a ,[b]) = merge (msort a) [b] msort' ( a , b ) = merge (msort a) (msort b) -- main = do putStrLn $ show $ qsort [13, 3, 5, 1, 5, 19, 67, 4, 19] putStrLn $ show $ qsort [15, 18 ,3, -4, 10, 67, 19 ,11]