ソート (sort) はある規則に従ってデータを順番に並べ換える操作のことです。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。
OCaml にはリストをソートする関数 List.sort がありますが、私達でも簡単に作ることができます。今回は「挿入ソート (insert sort)」と「クイックソート (quick sort)」を取り上げます。
挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、リスト [2; 4; 6] に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。
ソートするリストは tl で分解していくと空リストになります。これをソート済みのリストと考えて、ここにデータを挿入していきます。プログラムは次のようになります。
リスト 10 : 挿入ソート
let rec insert_sort xs =
let rec insert_element x = function
[] -> [x]
| (y::ys) as a -> if x < y then x::a else y::insert_element x ys
in
match xs with
[] -> []
| y::ys -> insert_element y (insert_sort ys)
関数 insert_sort は引数のリスト xs を再帰呼び出しで分解します。insert_sort を再帰呼び出ししてリスト ys をソートし、そのリストに先頭要素 y を関数 insert_element で挿入します。
局所関数 insert_element は再帰呼び出しでリストをたどり、データ x を挿入する位置を探します。引数のリストが空リストであれば、x が一番大きなデータです。リスト [x] を返します。これで、リストの最後尾に x を挿入することができます。次の節でリストを分解して、x が先頭の要素 y よりも小さい場合は、その位置に x を挿入します。そうでなければ、insert_element を再帰呼び出しします。
それでは実行してみましょう。
val insert_sort : 'a list -> 'a list = <fun>
# insert_sort [9; 1; 8; 2; 7; 3; 6; 4; 5];; - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でも「クイックソート (quick sort)」は高速なアルゴリズムとして有名です。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
[5; 3; 7; 6; 9; 8; 1; 2; 4]
5 を枢軸に分割
[3; 1; 2; 4] 5 [7; 6; 9; 8]
3を枢軸に分割 7を枢軸に分割
[1; 2] 3 [4] | 5 | [6] 7 [9; 8]
・・・分割を繰り返していく・・・
図 3 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。
リスト 11 : クイックソート
let rec quick_sort = function
[] -> []
| x::xs ->
let (m, n) = partition x xs in
quick_sort m @ (x :: quick_sort n)
最初の節が空リストの場合で、再帰呼び出しの停止条件になります。次の節でリストを分割してソートを行います。パターン x::xs でリストを分解し、リストの先頭要素 x を枢軸とします。
リストの分割は関数 partition で行います。partition は x を基準にリストを 2 つに分割し、それらのリストを組 (a, b) で返します。リスト a が枢軸よりも小さな要素を集めたもので、リスト b が枢軸以上の要素を集めたものです。なお、OCaml には同様の処理を行う関数 List.partition があります。List.partition は高階関数です。
quick_sort では let で局所変数 m と n を定義し、partition を呼び出して返り値をパターンで受け取ります。そして、quick_sort を再帰呼び出しして、リスト m, n をソートします。あとは、その結果を枢軸 x を挟んで結合すればいいわけです。
次はリストを分割する関数 partition を説明します。
リスト 12 : リストの分割
let rec partition n = function
[] -> ([], [])
| x::xs -> let (a, b) = partition n xs in
if x < n then (x::a, b) else (a, x::b)
最初の節が空リストの場合です。これが再帰呼び出しの停止条件になります。空リストの場合は 組 ([], []) を返します。次の節でリストを分割します。引数のリストをパターン x::xs で分解し、partition を再帰呼び出ししてリスト xs を 2 つに分割します。返り値は局所変数 (a, b) で受け取ります。
あとは、枢軸 n と要素 x を比較して、x が n よりも小さければ x をリスト a に追加して返します。そうでなければ、x をリスト b に追加して返します。これで枢軸 n を基準にしてリストを 2 分割することができます。
それでは、簡単な実行例を示しましょう。
val quick_sort : 'a list -> 'a list = <fun>
# quick_sort [5; 3; 7; 6; 9; 8; 1; 2; 4];; - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
正常に動作していますね。なお、partition は次のように末尾再帰でプログラムすることもできます。
リスト 13 : クイックソート
(* リストの分割 (末尾再帰) *)
let rec partition n a b = function
[] -> (a, b)
| x::xs -> if x < n then partition n (x::a) b xs
else partition n a (x::b) xs
let rec quick_sort = function
[] -> []
| x::xs ->
let (m, n) = partition x [] [] xs in
quick_sort m @ (x :: quick_sort n)
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するところまで劣化します。つまり、挿入ソートと同じくらい遅くなってしまうのです。たとえば、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。
このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。
ただし、この改良方法はリストには不向きであることに注意してください。リストはデータ数が多くなるほど、後ろのデータを取り出すのに時間がかかるようになります。先頭から 3 つのデータを取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。このため、リストのソートはクイックソートよりも「マージソート (merge sort)」の方が適しているといわれています。マージソートについては、あとで取り上げる予定です。
リスト : リストの分割とクイックソート
let rec partition_if pred = function
[] -> ([], [])
| x::xs -> let (ys, zs) = partition_if pred xs in
if pred x then (x::ys, zs) else (ys, x::zs)
let rec quick_sort = function
[] -> []
| x::xs ->
let (ys, zs) = partition_if (fun y -> y < x) xs in
quick_sort ys @ (x :: quick_sort zs)
val partition_if : ('a -> bool) -> 'a list -> 'a list * 'a list = <fun>
val quick_sort : 'a list -> 'a list = <fun>
# partition_if (fun x -> x mod 2 = 0) [1;2;3;4;5;6;7;8;9;10];; - : int list * int list = ([2; 4; 6; 8; 10], [1; 3; 5; 7; 9]) # quick_sort [5;3;7;4;6;8;2;9;1;0];; - : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9] # quick_sort [0;1;2;3;4;5;6;7;8;9];; - : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9] # quick_sort [9;8;7;6;5;4;3;2;1;0];; - : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]