ある小説の登場人物、あるいは、あるアーティストの曲といった集合について考えるとき、「それらの中で最も好きなものはどれですか?」という問いに答えることは (甲乙付け難くて悩むケースもあるかも知れませんが) 比較的簡単です。 しかし、「2番目に好きなものは?」「3番目に好きなものは?」...といった具合に質問を続けていくと、どんどん回答が困難になっていくはず。 最も嫌い (好きでない) ものについては、好きでないものと同じように簡単に答えられるので、最も特定が困難なのは、好きな (あるいは嫌いな) 順に並べたとき、そのシーケンスの中央に位置する要素だと言えるでしょう。

私はこれまで、プログラミングにおいてもこれと同様の問題が存在する、即ち、ある配列 (要素数n )について特定の指標に沿っての並べ替え (ソート) を行ったときに中央あるいはその付近に配置される要素を特定するには、ソートそのものと同じオーダ、つまり最低でも O(n logn ) の計算量が必要になると考えていました。 しかし実は、それはまったくの間違いで、選択アルゴリズムと呼ばれるものを使用すれば、線形、即ち O(n ) の計算量でこれを探し当てることができます。

このことは計算理論ではごく初歩的なトピックらしく、これまで知らなかったことについて大変恥ずかしくなってしまうわけですが、実際に調べていくとなかなかに複雑なものであることが判明。 そこで、自分なりに理解できたことをまとめて、ひとつのエントリとしてみることにしました。

選択アルゴリズムが指定された順位の要素を探し出す方法は、クイックソートの応用 (というか変形)。 クイックソートを知らない人がこの記事を読んでいるというのは考えにくいシチュエーションですが、説明の流れの整理のために簡単な説明を入れておくことにします。 例として、以下のような配列に対してソートを行うことを考えてみてください。

クイックソートではまず、配列に対して「ピボット (pivot)」と呼ばれる要素を設定します。 このとき、ピボットをどのように選ぶかは重要な問題となるのですが、ここではとりあえず、単純に中央に位置する、すなわち、floor((n - 1)/2) 番目の要素をピボットとして使うことにします。 (この例では n = 16 なので、7番目の要素 58 を使用。)

ピボットを設定したら、全ての要素を、ピボットより小さいものが前、ピボットより大きいものが後 (そして、ピボットはそれらの間) に配置されるよう並べ替えます。

これにより、配列全体が二つの未ソートの領域に分割されました。 (ピボット自身は最終的な位置に置かれている (これ以降移動されることはない) ので、未ソート領域からは除外する。) これらの領域それぞれについてピボットを設定して並べ替えを行い、さらにそうして分割された領域にピボットを設定して......といった具合にすべての未ソート領域の長さが1以下となるまで同じ操作を繰り返し適用することで、最終的に全ての要素が順番に並んだ状態へと到達することができます。

分割の反復は何回行われるのかを単純に見積もってみると、1回の分割で各領域は半分に分けられるので、長さn の配列ならばlog₂n 回程度分割すれば、すべての領域の長さが1になるでしょう。 一方、何回分割を行ったとしても、各領域の長さの合計、つまり配列全体の長さは変化しない (ピボットの長さは無視してください) ので、各分割後にピボットを設定して並べ替えを行う際には、配列全体で n 回の比較が発生することに。 クイックソートの計算量オーダが O(n logn ) = O(log₂n × n ) となるのは、概ねこうした理由からです。

ところで、上記の手法が O(n logn ) の計算量を必要とするのは、「ソート」を行う場合の話。 特定の位置に配置される要素を探し出す「選択」を目的とする場合には、この計算量を削減することが可能です。 例えば、ソート後に7番目となる要素を見付けたいのであれば、最初の分割の後は、ピボットの前方の領域に対してのみピボット繰り返しを適用すればよく、後方の領域に対しては以降の操作を行う必要はありません。 何故ならば、各要素は領域の境界 (ピボット) を越えて移動することはないので、目標とする位置を含む領域だけを対象として並び順を決定していけばよいからです。

7番目に小さい値は35であることが分かりました。 これが「クイックセレクト (en: quickselect)」と呼ばれるアルゴリズム。 疑い深い方のために、ソート後の配列を以下に示しておくことにします。

ところで、クイックセレクトの説明の中で「ピボットの選び方は重要」と述べましたが、これは一見簡単なようで、実は結構厄介な問題です。 分割に偏りが生じるような、極端な例を挙げれば、領域内の全ての要素がピボットより小さい (/大きい)、つまり、ピボットの前 (/後ろ) に並べ替えられてしまうようなピボットの選び方をしてしまうと、処理効率が著しく悪化してしまいます。 前セクションで示した配列に対して、領域の先頭にある要素をピボットとしてクイックセレクトを実行した場合の各分割ごとの進行は以下の通り。

最初の3回のピボット選択 (3, 77, 22) による領域分割の偏りが大きいため、求める結果を得るまでに必要な分割回数が増えてしまっていることが分かるでしょう。 この選び方に対しては、元の配列内の要素が降順 (大きいものから小さいものの順に) 並んでる場合が最悪ケースで、これが入力として与えられたときの計算量は O(n²) まで増加することに。 前セクションの例のように、領域の中央に位置する要素をピボットとして使う手法を採った場合でも、同様の問題は発生する可能性があります。 (先の例ではたまたま上手くいっただけ。)

理想的なピボットとは、領域の要素を半々に分ける、要するにそれらの半分よりも大きく、残りの半分よりも小さいような要素なのですが、これは中央値に他なりません。 (要素数が偶数の場合は、中央の2要素の平均ではなく、それらのうち前に位置する方を採用するものとする。) つまり、領域の長さ m に対して、ソート後に floor((m - 1)/2) 番目に配置される要素をピボットとして採用できれば最高のパフォーマンスが期待できるわけです。 となれば早速クイックセレクトを使って......としたいところですが、そもそもクイックセレクトをするために効率的なピボットの選択方法を探っていたわけで......堂々巡りになってしまいました。 無限ループって怖くね?

というわけで、ピボットの選択に中央値 (=クイックセレクト) を使うことはできないことが判明しました。 そこで、厳密な中央値を得ることは諦めて、かわりに「おおよその」中央値をピボットとする方法を考えることにします。 「おおよその」というのは、「厳密な中央値ではないけれど、その "付近" に配置される」という意味。 もっと厳密に言うならば、「ソート後に中央から前後にそれぞれ全体の長さの1/4 (25%) 以内に配置される」要素だということです。 この範囲を以下の図に緑色で示してみました。

では具体的にどうするのかというと、「中央値の中央値 (median of medians)」と呼ばれるものを求めます。 なんだか「王の中の王 (king of kings)」みたいな大仰な名前ですが、以下のアルゴリズムに目を通せば、このネーミングにも納得がいくはず。

まず配列を先頭から順番に (でなくても構わないのですが)、5つずつの要素からなるグループに分割します。 要素数が5の倍数でないときは余りが出ますが、それらは要素数1～4のグループとして特別に扱うもよし、ないものとして無視するもよし。 (この例では前者を選択。) 次にこれらのグループそれぞれについて中央値を求めます。 先程と同じ堂々巡りに陥ってしまいそうな気がしますが、この場合は各グループの要素数が5で固定されているので、ソートを行っても、その計算量オーダは O(5²) = O(1) であり、配列全体の要素数 n の影響を受けません。 全体のソートには、選択ソートなどの単純なアルゴリズムを使用するのが良いでしょう。 この各グループの中央値を集めて作った新しい配列の中央値が、中央値の中央値 M となります。 (この場合は M = 30 となる。)

中央値の数 (=グループ数) が5を超える場合は、その配列を更に5個ずつのグループに分割してそれぞれの中央値を求め、その数が5を超える場合はその配列を更に5個ずつの......といった具合に、再帰的に同じ手順を適用します。

このようにして求めた中央値の中央値がソート後に中央から±25%の範囲に収まる、というのはいったい何故でしょうか。 その理由を以下に図解してみました。

すべてのグループのうち、少なくとも半数の中央値はM 以下、残りの半数の中央値はM 以上となります。 そして、M 以上の中央値を持つグループでは少なくともその要素の半数 (青で図示されているもの) がM以下の値を、同様に、M 以上の中央値を持つグループでは少なくともその要素の半数 (赤で示されている) がM以上の値を持ちます。

この余り要素を含め、白で示されたブロックは、M より小さくも大きくもなり得る要素。 これらがどれくらいの割合で M の前後に配分されるかが、結果の良否を決定します。 それでは、このM = 30 が真の中央値からどれだけ離れているを確かめるため、配列全体をソートしてみましょう。

白で示た要素が全てM よりも大きく、後方に配置されてしまったために、M の位置が前方に大きく偏ってしまいました。 これは最悪の結果ですが、しかしその場合であっても、前後の端から25%の範囲に入ることがない、というのが「中央値の中央値」の特性です。

もう少しイメージを掴みやすくするため、要素数を25としてグループの数を5に増やした上で、再び中央値の中央値 M を求めてみましょう。

今度は M = 38 となりました。 先程と同じようにグループをその中央値の大きさの順に並べてみるとこんな具合。

前回とは対照的に、白で示された要素がM の前後にきれいに半分ずつ振られたため、M がソート後の配列のちょうど中央に配置されました。 これは最良の結果です。

要素数n の配列に対して、中央値の中央値を求めるために必要な計算量のオーダは幾らになるでしょうか。 単純に考えると、配列の要素を5つずつ、n/5個のグループに分けて、これらから抽出した (n/5個の) 中央値から成る配列をソートすることになるわけですから、

となってしまうように思われます。 しかし、先に説明したように、グループの数n/5 が5よりも大きい場合は、抽出された中央値の配列をさらに5つずつの要素に分割するという再帰的な手順を経ることを思い出してください。 グループへの分割→中央値の抽出という操作k 回行えば、要素の数は5^k分の1 (5^-k倍) になります。 これは指数関数的減衰であり、O(n²) の発散を押さえ込んで収束するため、実際のオーダはたかだか線形 O(n ) となります。 厳密な証明をしようとするとかなり入り組んだ話になるので、詳細に関しては以下を参照してください。 (ザ・丸投げ!!)

「中央値の中央値」を求めることで、最悪のケースでも O(n ) の計算量でそこそこに「良い」ピボットを選ぶことができるようになりました。 これを用いてクイックセレクトを行えば、安定して O(logn + n ) = O(n ) の計算量で任意の順位の要素を選択することができます。

ところで、クイックセレクトのアルゴリズムを少しばかり変形することで、配列の任意の要素が全体の中で何番目に小さな (大きな) 値を持つのかを O(n ) の計算量で求めることができるのですが、そうしたアルゴリズムについては何か名前は付いていないのでしょうか。 ご存知の方がいらっしゃいましたら、ご教示ください。