## 2009-12-04

### Shell Sort (?)

01:23

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 を使えばよかったかも

パターンマッチが多すぎてカッコわるいと言われたので 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)
```

もう何が何だか…