#はじめに
ソートのアルゴリズムは通常、実数における通常の順序関係のように全順序である順序関係に対して行うものですが、本記事では半順序に対するソートのアルゴリズムについて解説します。
#半順序とは
集合X上の二項関係 ≦ が半順序であるとは、以下の性質を満たすものとして定義されます。
- 反射律 任意のx $\in$ Xに対し、x ≦ x を満たす。
- 反対称律 任意のx, y $\in$ Xに対し、x ≦ y かつ y ≦ x ならば x = yを満たす。
- 推移律 任意のx, y, z $\in$ Xに対し、x ≦ y かつ y ≦ z ならば x ≦ zを満たす。
ここに全順序律 任意のx, y $\in$ Xに対し、x ≦ y または y ≦ x を満たすこと追加したものを全順序と言います。
通常、ソートを行うアルゴリズムはこの全順序関係を仮定した上で成り立つアルゴリズムです。しかし以下のような半順序でソートしたいときはどうすればいいでしょうか？
##半順序の例
半順序の例としては、以下のようなものが考えられます。
- 集合の包含関係。すなわち集合Aを固定したとき、Aの部分集合X, YがX $\subset$ Yを満たすときにX ≦ Yと定めると、≦は半順序となる。
- 複素数における以下の演算法則を満たす半順序。
- 任意の複素数x, y, aに対し、x ≦ y ならば a + x ≦ a + y を満たす。
- 任意の複素数x, y, aに対し、x ≦ y かつ 0 ≦ a ならば ax ≦ ay を満たす。
2つ目の複素数の例ですが、これらの演算法則を満たす全順序は存在しません1。しかし半順序であれば、複素数x = a + ib, y = c + idに対し、x ≦ y を b = d かつ a ≦ b (この≦は実数における大小関係)、すなわち虚部が一致する場合のみ実部の大小で順序を定めると、半順序の性質を満たします。後で説明する例はこの半順序で解説します。
##そもそも半順序において「ソートされている」とは？
全順序において、有限列がソートされているとは以下のようなものを言います。
- 有限列 a1, ..., an がソートされているとは、i ≦ j ならば ai ≦ aj を満たすこと。
しかし半順序では、比較不能な場合、すなわち x ≦ y も y ≦ x も成り立たない場合があるので、この定義を満たす並び替え列が存在しない場合があります。そこで半順序でもソート列が存在するように、ソートされている状態を以下のように再定義します。
- 有限列 a1, ..., an がソートされているとは、 i ≦ j かつ aj ≦ ai ならば ai ≦ aj を満たす2。
これは数列の手前には比較不能な要素はあってもいいが、真に大きい要素は存在しない状態を意味しています。さらに≦が全順序の場合は、元のソートされている定義と同値になります。この定義ならば半順序でもソートされた列に並び替えられることが保証できます。ただし、半順序のときは一般にソートされた列の一意性が成り立たたず、ソートされている状態が複数存在する場合があることに注意が必要です。
今回紹介するのは、ソートされた列のうちの１つを返すアルゴリズムです。
#アルゴリズム
半順序でソートするアルゴリズムとして考えられるのは、以下の２つです。
- 有限列の各要素を点として、半順序関係で有向グラフを定義し、トポロジカルソートを使う。
- 全順序のときの通常のソートアルゴリズムを流用する。
##トポロジカルソートを使う場合
トポロジカルソートを使うには、有向グラフに閉路が存在しないことを仮定する必要があります。ここで、グラフに閉路が存在することと有限列に同じ要素があることが同値になるので、有限列に存在する各要素が現れる回数をカウントしておいて、この要素でグラフを作ればいいです。要素数カウントの計算量は、有限列の長さnに対してO(n)になります。
しかしそこからが問題で、トポロジカルソートの計算量はグラフの点の集合V、辺の集合Eに対し、O(|V|+|E|)となります。しかし、これを達成するには辺の集合Eが求めないといけないわけですが、関係≦からEを求めるのに必要な計算量がO(n^2)となるため、全体の計算量もO(n^2)となってしまいます。
そこで、O(n log n)の全順序におけるソートアルゴリズムが流用できないかを考察していきます。
##全順序におけるソートアルゴリズムは使えるか
平均計算量がO(n log n)の代表的なソートアルゴリズムであるマージソート、クイックソート、ヒープソートに対し、半順序においてもソートできるかどうかを確認します。
###マージソート
半順序におけるマージソートのアルゴリズムは全順序のときとほとんど同じです。
[アルゴリズム]
- 与えられた有限列を長さの差が高々１になるように２つに分割する。
- それぞれ分割した列をソートし、それぞれ列１、列２とする。
- 列１と列２をマージする。すなわち、列１と列２の先頭要素を比較し、列１の方が小さければ列１の先頭要素、そうでなければ列２の先頭要素を返り値の先頭要素とし、残りの列１、列２でマージしたものを後ろにつなげる。
このアルゴリズムは全順序であればもちろんソートできるのですが、半順序ではソートされない例があります。
反例：複素数上の半順序によるソート
[i, 0, 1, 2]をマージソートすると[1, 2, i, 0]となりますが、1 > 0 よりソートされていない。
###クイックソート
クイックソートのアルゴリズムも全順序のときと同じです。
[アルゴリズム]
- 与えられた有限列の先頭要素を取り出し、それを基準値とする。
- 残りの列の要素に対し、基準値より小さいもの全体の列１と、そうでないものの列２を作る。
- 列１、列２をそれぞれソートし、列１、基準値、列２の順でつなげる。
実はクイックソートのアルゴリズムならば半順序であってもソートできます。
証明は、列１、列２がそれぞれソートされており、列１の全ての要素が基準値以下であると仮定したとき、列１、基準値、列２の順でつなげたものもソートされていることを示せばいいです。
証明の詳細は「クイックソートは半順序でもソート可能であることをCoq/SSReflectで証明する」をご覧ください。
###ヒープソート
ヒープソートのアルゴリズムを半順序上で定義するためには、３つの要素における最大値を定義しなくてはいけません。半順序において最大値が存在するとは限らないので、これを極大値で代用することにします。ここでいう極大値とは、その値より真に大きい値が存在しないことを指します。
[アルゴリズム]
- 列から二分木を作成する。
- 二分木を整列する。すなわち、各親ノードに対し、親ノードが極大値でない場合、親ノードの値と極大値をとるような実子ノードの値を入れ替える。最終的に、各親ノードはその実子ノードとの極大値の状態になるようにする。
- 整列した二分木の根の値を取り出し、ヒープソートの返り値の最後尾に加える。
全順序の場合はもちろんこのアルゴリズムでソートできるのですが、半順序の場合は反例が存在します。
反例：複素数上の半順序によるソート
[1, 2i, i, 2]をヒープソートすると[2i, i, 2, 1]となるが、2 > 1 よりソートされていない。
##アルゴリズムのまとめ
全順序におけるO(n log n)のソートアルゴリズムが半順序の場合でも使えるかどうかは以下の表の通りです。
| ソートの種類 | 可否 |
|---|---|
| マージソート | × |
| クイックソート | ○ |
| ヒープソート | × |
マージソートとヒープソートでソートできなかったのは、マージソートとヒープソートにおけるソート可能性の証明で用いるであろう「極大値の推移性」すなわち以下の性質が半順序では一般に成り立たないからです。
- 任意のX上の有限部分集合の有限集合族{X1 , ..., Xn}に対し、各Xiの極大値1つをxiとする。このとき、集合{x1, ..., xn}の極大値の1つをxとしたとき、xは$\bigcup$Xiの極大値である。
しかし、クイックソートにおける証明では極大値を使用せず、この性質を仮定しません。クイックソートでうまくいった理由の一つはこれです。
さらに、クイックソートならば半順序だけでなく擬順序でもソートできます。擬順序とは、反射律、推移律のみ仮定した二項関係で、これに反対称律を追加したものが半順序となります。
#まとめ
通常、ソートアルゴリズムは全順序において定義されるものですが、本記事では半順序でソートする場合のアルゴリズムに関して考察しました。
結果として、半順序でソートするにはクイックソートが使えるということが判明しました。