ソートのお話です。今まで例題としてクイックソートと挿入ソートを取り上げました。データ数を N とすると、挿入ソートの実行時間は N2 に比例します。挿入ソートは遅いソートですが、クイックソートは高速なソートで、実行時間は N * log2 N に比例します。
ところが、クイックソートにも弱点があり、枢軸の選び方によっては実行時間が N2 に比例する「遅いソート」になってしまいます。リストの場合、枢軸を自由に選ぶことが難しいので、クイックソートはリスト向きのアルゴリズムとはいえません。
そこで、今回はリストに適したソートアルゴリズムである「マージソート (merge sort)」を取り上げます。データ数を N とすると、マージソートの実行時間は N * log2 N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。ただし、クイックソートと違って、データによって性能が劣化することはありません。どのようなデータに対しても力を発揮してくれます。
まず最初にマージから説明します。マージ (併合) とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。
┌─ [1, 3, 5] : リスト a
[] ←┤
└─ [2, 4, 6] : リスト b
小さい方をセットする
┌─ [3, 5] : リスト a
[1] ←┘
[2, 4, 6] : リスト b
1 をセットする
[3, 5] : リスト a
[1, 2] ←┐
└─ [4, 6] : リスト b
2 をセットする
データがなくなるまで繰り返す
図 : リストのマージ
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
それでは、実際にプログラムを作ってみましょう。次のリストを見てください。
リスト : リストのマージ merge_list :: Ord a => [a] -> [a] -> [a] merge_list [] ys = ys merge_list xs [] = xs merge_list a@(x:xs) b@(y:ys) | x <= y = x : merge_list xs b | otherwise = y : merge_list a ys
関数 merge_list の引数 xs, ys がマージするリストです。最初の節はリスト xs が空リストになった場合で、リスト ys をそのまま返します。2 番目の節はリスト ys が空リストになった場合で、リスト xs をそのまま返します。この 2 つが再帰呼び出しの停止条件になります。
リスト xs と ys にデータがあれば、先頭要素 x と y を演算子 <= で比較します。返り値が真であれば x を、そうでなければ y を merge_list が返すリストに追加します。merge_list を再帰呼び出しするとき、追加する要素をリストから取り除くことに注意してください。これでリストをマージすることができます。
簡単な実行例を示しましょう。
ghci> merge_list [1,3,5,7,9] [2,4,6,8,10] [1,2,3,4,5,6,7,8,9,10] ghci> merge_list [1,3,5,7,9] [] [1,3,5,7,9] ghci> merge_list [] [1,3,5,7,9] [1,3,5,7,9] ghci> merge_list [1,3,5,7,9] [2,4,6] [1,2,3,4,5,6,7,9] ghci> merge_list [1,3,5] [2,4,6,8,10] [1,2,3,4,5,6,8,10]
マージソートは、このマージを使ってデータをソートします。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。
実際にプログラムを作る場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。
再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。
リスト : マージソート
merge_sort :: Ord a => Int -> [a] -> [a]
merge_sort _ [] = []
merge_sort 1 (x:_) = [x]
merge_sort 2 (x:y:_) = if x > y then [y, x] else [x, y]
merge_sort n xs =
merge_list (merge_sort m xs) (merge_sort (n - m) (drop m xs))
where m = div n 2
関数 merge_sort の第 1 引数がリストの長さ、第 2 引数がソートするリストです。merge_sort はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。
引数 x
｜
｜←── 長さn ──→｜
（１ ２ ３ ４ ５ ６ ７ ８）
｜←n/2→｜ ｜←n/2→｜
｜ ｜
引数 x 引数 y 再帰呼び出し
図 : リストの分割
merge_sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は x と n / 2 で表し、後半部分を y と n / 2 で表します。y はリスト x の先頭から n / 2 個の要素を取り除けば求めることができます。この処理は Haskell に用意されている関数 drop を使うと簡単です。
drop :: Int -> [a] -> [a]
drop n xs はリスト xs の先頭から n 個の要素を取り除きます。xs に対して n 回だけ tail を適用すると考えてもかまいません。簡単な例を示しましょう。
ghci> drop 3 [1,2,3,4,5] [4,5] ghci> drop 0 [1,2,3,4,5] [1,2,3,4,5] ghci> drop 5 [1,2,3,4,5] []
あとは再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。リストの長さが 2 の場合は簡単なので、2 つの要素を比較してソート済みのリストを作成して返します。そして、merge_sort の返り値を merge_list でマージすればいいわけです。
それでは実行してみましょう。
ghci> merge_sort 10 [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] ghci> merge_sort 10 [9,8,7,6,5,4,3,2,1,0] [0,1,2,3,4,5,6,7,8,9] ghci> merge_sort 10 [0,1,2,3,4,5,6,7,8,9] [0,1,2,3,4,5,6,7,8,9]
正常に動作していますね。
リストを二分割していくのではなく、要素が 1 つのリストを作って、それを順番にマージしていくこともできます。次のリストを見てください。
リスト : マージソート (別解)
merge_sort' :: Ord a => [a] -> [a]
merge_sort' xs = iter1 (map (:[]) xs)
where
iter1 [x] = x
iter1 xs = iter1 (iter2 xs)
iter2 [] = []
iter2 [x] = [x]
iter2 (x:y:zs) = merge_list x y : iter2 zs
実際の処理は局所関数 iter1 と iter2 で行います。最初に、map で要素をリストに格納して、それを iter1 に渡します。iter1 はリストの要素がひとつになるまで、iter2 を繰り返し呼び出します。iter2 は先頭から順番にリストを 2 つ取り出して、それを merge_list でマージします。そして、その結果をリストに格納して返します。
それでは実行してみましょう。
ghci> merge_sort' [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] ghci> merge_sort' [0..9] [0,1,2,3,4,5,6,7,8,9] ghci> merge_sort' [9,8..0] [0,1,2,3,4,5,6,7,8,9]