星期四, 3月 11, 2010

Haskell Practice - Merge Sort

老實說我也不太清楚是不是 Merge Sort ,只是照著感覺寫,而且感覺是效率不佳的 Merge Sort ... Orz,其中的 merge 是 scm 老師寫的,他寫了一封信,我很認真的看再很認真的忘掉再重寫中。

insertionSort [] = []
insertionSort (x:xs) = merge [x] (insertionSort xs)

merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) 
    | x <= y = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

測試結果如下:

*Main> mergeSort [3,1,5,2,6, -1, 10]
[-1,1,2,3,5,6,10]

---
想要改寫,不過應該是晚上的事了。


事情比想像中更糟,自己推一次,發現根本不是 Merge Sort 啊 ... Orz


上面那個應該是 insertion sort ... 緊急之間寫了下面這個 code 出來,但是會出錯 ... meeting 在即,等回來再說了 ...

mergeSort [] = []
mergeSort x = 
    if length x > 1 then 
        merge (mergeSort (fst (splitAt half x))) (mergeSort (snd (splitAt half x)))
    else x
    where half = truncate ( (fromIntegral (length x))/ (fromIntegral 2))

看起來是沒有出錯了,接下來該開始思考怎麼寫會比較好一點 XD。


2010/03/12 00:09 結果根本就在惡補怎麼操作 list ,發現自己是有看了,但是都忘完了 ... 到目前為止的版本

mergeSort (x:xs) 
    | xs == [] = [x]
    | otherwise = merge (mergeSort (take half (x:xs))) (mergeSort (drop half (x:xs)))
    where half = truncate ( (fromIntegral (length (x:xs)))/ (fromIntegral 2))

2009/03/12 10:19 AM 只是嘗試將 length 帶入 argument 中,實質上並無太大改變,我一直在想著長度的問題 ... 可是腦袋又是空掉了 ...

mergeSort [] = []
mergeSort x = mergeSort' x (length x) 

mergeSort' x l
    | l == 1 = x
    | otherwise = merge (mergeSort' (take half x) half) (mergeSort' (drop half x) (l-half))
    where half = truncate ((fromIntegral l)/(fromIntegral 2))

2009/03/14 11:38 pm 依 scm 在 comments 裡的建議把 uninterleave 寫出來,自己重寫 interleave ,發現有一點不太一樣(還好功能一樣 XD)
interleave [] ys = ys
interleave xs [] = xs
interleave (x:xs) (y:ys) = x:y:(interleave xs ys)
-- interleave (x:xs) (y:ys) = x:(interleave (y:ys) xs)

uninterleave :: [a] -> ([a],[a])
uninterleave [] = ([], [])
uninterleave (x:xs) = uninterleave' (x:xs) [] [] 

uninterleave':: [a] -> [a] -> [a] -> ([a], [a])
uninterleave' [] ys zs = (zs, ys)
uninterleave' (x:xs) ys zs = uninterleave' xs zs (x:ys)

mergeSort2 :: (Ord t) => [t] -> [t]
mergeSort2 [] = []
mergeSort2 (x:[])  = [x]
mergeSort2 xs = merge (mergeSort2 (fst (uninterleave xs))) (mergeSort2 (snd(uninterleave xs)))

張貼留言