Selecting median using Quick Select Algorithm(1)

先日のエントリではメディアンの選択にsort()を用い、より効率のよいメディアンの選択方法を課題としました。

さて、今回そのアイデアの一つとして紹介するのはQuick Selectというアルゴリズムです。Quick Selectというアルゴリズム名は一般的ではないかもしれません。また、原典でも異なる呼称がなされている可能性があります。

Quick Selectはかの有名なアルゴリズム、Quicksortの分割部分を利用したアルゴリズムです。QuicksortはC. A. R. Hoareから1962年にComputer Journalにて発表されており、先日紹介したkd木と同様、1980年代に書かれた名著アルゴリズム Cに取り上げられています。日本語版では第1巻、整列のクイックソートの章に掲載されています。

Quick Selectは以下のような特徴を持っています。

  • 平均的に線形時間で走る
  • 破壊的である(副作用としてデータを部分的に整列してしまう)

Quick Selectを理解するにあたって、まずはQuicksortを理解しなければなりません。Quicksortは事実上世界一有名なアルゴリズムとも言えるため、秀逸な資料を数多く見つけることが出来ます。

以下はアルゴリズム Cから抜粋したクイックソートのコードです。

quicksort(int a[], int l, int r)
{
  int v, i, j, t;
  if (r > l) {
    v = a[r]; i = l-1; j = r;
    for (;;) {
      while (a[++i] < v) ;
      while (a[--j] > v) ;
      if (i >= j) break;
      t = a[i]; a[i] = a[j]; a[j] = t;
    }
    t = a[i]; a[i] = a[r]; a[r] = t;
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }
}

Quicksortは分割統治法に基づく整列アルゴリズムです。データを2つに分割し、それぞれの部分を独立に整列することを繰り返すことにより全体を効率よく整列することが出来ます。また、アルゴリズム Cにはアルゴリズムの流れをより明確に表現するため、以下のようなコードも掲載されています。

quicksort(int a[], int l, int r)
{
  int i;
  if (r < l) {
    i = partition(l, r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }
}

随分とコードの見通しがよくなりましたね。partition()は、その名の通りデータの分割を行う関数です。破壊的な関数であることに注意してください。

さて、ここで分割の定義を見てみましょう。以下もアルゴリズム Cからの抜粋です。

この方法の中心はpartition手続きである。この手続きは、配列を並べ替えて次の条件を満たすようにする。

(1) あるiに対して要素a[i]が最終位置にある
(2) a[l]、...、a[i-1]の全ての要素はa[i]より小さいか等しい
(2) a[i+1]、...、a[r]の全ての要素はa[i]より大きいか等しい

この定義のみではなんだかよく分からないですね。アルゴリズム Cでは見事な解説が続くので、是非ご一読ください。

さて、分割の条件について考えてみましょう。分割が満たすべき状態は、データのある値を基準にし、その値より小さい値を基準の値の左側に、大きい値を基準の値の右側に配置することを差しています。

勿論そのためにはまず基準の値を選択しなければなりません。基準の値はピボットとも呼ばれ、Quicksortの性能に関わる重要な要素です。

Quicksortの性能を上げるために、ピボットの選択には様々な手法が考案されています。本エントリでは、アルゴリズム Cでの解説にも用いられている、データの一番右側の値を基準の値、すなわちピボットとして選択する方法を用いて説明を進めてみることにします。この手法は、私の好みの実装でもあります。


さて、以下のデータを整列することを考えてみましょう。アルゴリズムには勿論、Quicksortを用います。

まず基準となる値、ピボットを選択します。今回はデータの一番右側に位置する値をピボットとするのでした。これを赤色で可視してみます。

次に、ピボットの値より大きい値を薄い灰色で、また、小さい値を濃い灰色で可視してみましょう。

なかなか分かりやすくなりました。ピボットより小さい値と大きな値を数えてみると、それぞれ5個と7個ですね。そのため、データが次のような状態になれば分割は終了すると考えてよさそうです。

さて、では分割を考えてみましょう。元のデータは以下のような状態でした。

Quicksortでは、配列の最も左側から右側に向け、ピボットの値より大きい値を検索します。それと同時に、ピボットの一つ左側の要素から左側に向け、ピボットより小さい値を検索します。

まずは、左側からの検索を考えてみます。この例では左端の値、62がピボットよりも大きい値のようですね。

62に、ピボットより大きいことを示すマークを付けておきます。

次に、ピボットの一つ左側の要素から左側に、ピボットより小さな値を検索してみましょう。ピボットから見て、2つ左に位置する値43はピボットの値よりも小さいですね。

こちらにも、ピボットより小さい値であることを示すマークを付けておきます。

さて、左右からの検索がそれぞれ終了しました。マークが示す値を比較してみましょう。大きな値が小さな値の左側にあるのは分割の終了条件から反します。値を交換してしまいましょう。

先ほどより、条件に近い配列になりましたね。

ここで、可視に工夫をしてみます。マークを残し、交換を示す結線を追加しましょう。

では検索を続け、新しいマークを付けてみます。

この状態も分割の終了条件に反しますので値の交換を行い、検索を続けます。

この時点でピボットより小さい値群と大きい値群に分けることが出来たようです。このままQuicksortは検索を続けます。

ピボットの値よりも大きな値と小さな値がマークされていますが、先ほどと様子が異なります。これらマークの付いた値はすでに整列しています。2つのマークの位置関係が逆転していることで、これを判断することが出来ます。

残る分割の仕事は、より大きい値であることを示すマークが付いた値とピボットの値を入れ替えることです。

さて、分割の目標としていた状態が出来ました。予想していた通り、ピボットの左側にはピボットの値より小さい値が5つ、ピボットの右側にはピボットの値より大きい値が7つ並んでいます。

ここでデータをじっくり観察してみましょう。ピボットの左側、すなわちピボットの値より小さい値の集まりを見てみましょう。ほとんど整列しているようですが、まだ完全に整列はされてません。また、ピボットより右側、すなわちピボットの値より大きい値の集まりを見てみましょう。こちら側はあまり整列されていないようですね。

ここで、左右のデータをそれぞれ再帰的にQuicksortを用いて整列してみます。先ほどと同様に、それぞれのデータの集まりにおいて、ピボット自身、ピボットの値より小さい値およびピボットの値より大きい値で色を分けて可視しています。

それぞれのデータに関して先と同様の検索を行い、必要であれば交換をします。左側のデータはすでにほとんど整列していたため、ピボットと大きい値のマークが付いた値の交換が行われ、分割が終了しているようです。

後は再帰的に整列を行う必要がなくなるまで分割および整列を繰り返します。

再帰的な呼び出しが全て終了した時点でデータは整列されています。これがQuicksortアルゴリズムを用いた整列です。


さて、今回のエントリではkd木の可視と同様に、PostScriptを用いて可視化を行っています。PostScriptファイルを生成しているのはPythonコードです。そのため、それなりに大きいデータを可視化することも比較的容易です。以下は要素数が32のデータの可視となります。

先ほどまでの例よりも整列する様が観察しやすいよう思います。この当たりはPostScriptを用いた可視化の醍醐味の一つです。


次回はここまでに紹介したQuicksortの分割アルゴリズムの利用をした、Quick Selectアルゴリズムを紹介したいと思っています。

参考

このエントリを作成するに至った動機はkd木の可視でした。

追記

Selecting median using Quick Select Algorithm(2) - agwの日記として、続編を記載しました。