今日はリストの挿入ソートについて考える。 Haskellでの実装を念頭に置いて、ループを再帰で考える。 挿入ソートを再帰で実装するには、以下の2つのパートが考えられる。
- 値とリストを受け取り、リストの適切な場所に値を挿入する(挿入の処理)
- リストを受け取り、1.に先頭の要素と2.でソート済みのリストを渡す(挿入ソートの処理)
便宜的に1.の処理をinsert、2.の処理をisortと呼ぶことにする。
処理を詳細に考えていく。 insertとisortは共に再帰的な関数である。
まず1.の挿入の処理。
-
xの空リストへの挿入は、xのみを含むリストを返す - 空でないリストへの挿入では、リストを先頭要素
yとそれ以降ysに分割する -
xがリストの先頭要素y以下なら、x、ys、yのリストを返す -
xがリストの先頭要素より大きければ、yと再帰的にysにxを挿入した結果のリストを連結して返す
続いて2.の挿入ソートの処理。
- 空のリストの挿入ソート結果は空のリストである
- 空でないリストの挿入ソート結果は、リストの先頭要素
xを、それ以降xsを再帰的に挿入ソートした結果に挿入したものである
Rubyで実装すると以下のイメージとなる。
def insert(x, list)
if list.length == 0
list << x
else
y = list[0]
ys = list[1..-1]
if x <= y
[x, y] + ys
else
[y] + insert(x, ys)
end
end
end
def isort(list)
if list.length == 0
[]
else
x = list[0]
xs = list[1..-1]
insert(x, isort(xs))
end
end
p isort([2, 4, 3, 5, 1])
[1, 2, 3, 4, 5]
これをHaskellで実装する。 挿入ソートを再帰で実装する考え方は上記で述べたため、ループを再帰にする事はすでにできている。 あとは分岐をガード式に読み替えて、Haskellのコードに落としてゆくだけだ。
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x <= y = x : y : ys
| otherwise = y : insert x ys
isort :: Ord a => [a] -> [a]
isort [] = []
isort(x:xs) = insert x (isort xs)
main = print $ (isort [2, 4, 3, 5, 1])
[1,2,3,4,5]
以上のように挿入ソートをHaskellで実装することができた。 だんだんHaskellの考え方が身についてきた。 ポイントは、以下の2点である。
- ループを再帰として考えること
- 条件分岐をガードとして考えること
ところで闇雲にHaskellを勉強するのはしんどいので、少し前からプログラミングHaskellを購入し、これを元に勉強を進めている。これも簡単な内容とは言いがたいのだが、HaskellのHもわからない人には心強い本である。おすすめ。
