Insertion Sort と Merge Sort をやって、次に何をやろうかなーと思って調べてたら、Shell Sort がおもしろそうだったのでやってみる。
ただし、よく見るような
h(n+1) = 3*h(n)+1 -> 1, 4, 13, 40, 121, ...
の数列を使うものではなくて、
h(n) = 3^(n-1) -> 1, 3, 9, 27, 81, ...
でやった。
ロジックは前にやった Insertion Sort と Merge Sort (非安定版) の組み合わせなので簡単。
リストの長さが9以下のものは Insertion Sort に切り替え。
import List -- shell sort shellSort :: Ord a => [a] -> [a] shellSort = shellSortBy compare shellSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] shellSortBy _ [] = [] shellSortBy _ [x] = [x] shellSortBy cmp [x,y] = if cmp x y == GT then [y,x] else [x,y] -- do insertion sort if list is short shellSortBy cmp xs@([x1,x2,x3]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7,x8]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7,x8,x9]) = insertionSortBy cmp xs -- else split into 3, shell sort each, then insertion sort the whole shellSortBy cmp xs = insertionSortBy cmp $ merge3 (shellSortBy cmp as) (shellSortBy cmp bs) (shellSortBy cmp cs) where (as,bs,cs) = split3 xs split3 :: [a] -> ([a], [a], [a]) split3 [] = ([],[],[]) split3 [x] = ([x],[],[]) split3 [x,y] = ([x],[y],[]) split3 (a:b:c:xs) = (a:as, b:bs, c:cs) where (as, bs, cs) = split3 xs merge3 :: [a] -> [a] -> [a] -> [a] merge3 [] [] [] = [] merge3 [x] [] [] = [x] merge3 [x] [y] [] = [x,y] merge3 (x:xs) (y:ys) (z:zs) = x:y:z:(merge3 xs ys zs) -- insertion sort insertionSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] insertionSortBy cmp [] = [] insertionSortBy cmp (x:xs) = insertBy cmp x $ insertionSortBy cmp xs main = print $ shellSort [23,4,5,43,6,3,2,94,3,2,63,68,95,33,22,67,4,2,67,47,89,53,26,83,56,78,96,4,32,12,45,67,45,3,68,94,21,56,7,85,3,21,6,83,24,79,34,23,32,76,54,1,24,64,98,62,19,63,28,36,18,52]
↓実行。
h(n+1) = 3*h(n)+1 -> 1, 4, 13, 40, 121, ...
を使うにはどうしたらいいのだろう。うーん…
パターンマッチが多すぎてカッコわるいと言われたので null.drop にしてみた。
shellSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] shellSortBy _ [] = [] shellSortBy _ [x] = [x] shellSortBy cmp [x,y] = if cmp x y == GT then [y,x] else [x,y] shellSortBy cmp xs = if null (drop 9 xs) then insertionSortBy cmp xs else insertionSortBy cmp $ merge3 (shellSortBy cmp as) (shellSortBy cmp bs) (shellSortBy cmp cs) where (as,bs,cs) = split3 xs
うちの環境ではインタープリタでもコンパイルしてもこっちのほうが速くなるっぽい。
h(n+1) = 3*h(n)+1 -> 1, 4, 13, 40, 121, ...
を使う版を作ってみた。
パフォーマンスは考えない方向で。
import List -- shell sort shellSort :: Ord a => [a] -> [a] shellSort = shellSortBy compare shellSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] shellSortBy cmp xs = insertionSortBy cmp $ shellSortBy' 4 cmp xs shellSortBy' :: Ord a => Int -> (a -> a -> Ordering) -> [a] -> [a] shellSortBy' n cmp xs = if null (drop (n*9) xs) then merge $ map (insertionSortBy cmp) $ split n xs else merge $ map (insertionSortBy cmp) $ split n $ shellSortBy' (n*3+1) cmp xs split :: Int -> [a] -> [[a]] split n xs = split' xs [] $ replicate n [] split' :: [a] -> [[a]] -> [[a]] -> [[a]] split' [] xss yss = (reverse xss) ++ yss split' xs xss [] = split' xs [] $ reverse xss split' (x:xs) xss (ys:yss) = split' xs ((x:ys):xss) yss merge :: [[a]] -> [a] merge xss = merge' [] xss merge' :: [[a]] -> [[a]] -> [a] merge' [] [] = [] merge' xss [] = merge' [] $ reverse xss merge' xss ((y:[]):yss) = y : (merge' xss yss) merge' xss ((y:ys):yss) = y : (merge' (ys:xss) yss) -- insertion sort insertionSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] insertionSortBy _ [] = [] insertionSortBy _ [x] = [x] insertionSortBy cmp [x,y] = if cmp x y == GT then [y,x] else [x,y] insertionSortBy cmp (x:xs) = insertBy cmp x $ insertionSortBy cmp xs main = print $ shellSort [23,4,5,43,6,3,2,94,3,2,63,68,95,33,22,67,4,2,67,47,89,53,26,83,56,78,96,4,32,12,45,67,45,3,68,94,21,56,7,85,3,21,6,83,24,79,34,23,32,76,54,1,24,64,98,62,19,63,28,36,18,52]
reverse しまくり、length (相当の null drop (n*9) ) しまくり。
たぶんアルゴリズム的には手続き型言語のと同じになってると思う。
import Data.List (transpose, insert) -- Insertion sort, for sorting columns. insertionSort :: Ord a => [a] -> [a] insertionSort = foldr insert [] -- Splits a list into k columns. columnize :: Int -> [a] -> [[a]] columnize k = transpose . takeWhile (not . null) . map (take k) . iterate (drop k) -- Merges columns back into a single list. decolumnize :: [[a]] -> [a] decolumnize = concat . transpose -- Each phase of the Shell sort breaks the list into k columns, sorts each with an -- insertion sort, then merges those columns back into a list. shellSortPhase :: (Ord a) => Int -> [a] -> [a] shellSortPhase k = decolumnize . map insertionSort . columnize k -- The full Shell sort, applying phases with arbitrarily large gap sizes according to -- R. Sedgewick, J. Algorithms 7 (1986), 159-173 shellSort :: (Ord a) => [a] -> [a] shellSort xs = foldr shellSortPhase xs gaps where gaps = takeWhile (< length xs) sedgewick sedgewick = concat [[9 * 2^n - 9 * 2^(n `div` 2) + 1, 8 * 2^(n+1) - 6 * 2^(n `div` 2) + 1] | n <- [0..]]
transpose を使うのは思いつかなかった。
1,11,10,27,19,53,55,117,109,233,253,489,505,977,...
という数列を使うらしい。
これと同じことをやってるらしい↓。
import Data.List shellSort xs = foldr (invColumnize (map (foldr insert []))) xs gaps where gaps = takeWhile (< length xs) $ iterate (succ.(3*)) 1 invColumnize f k = concat. transpose. f. transpose . takeWhile (not.null). unfoldr (Just. splitAt k)
もう何が何だか…