k 番目の要素の選択

説明

select は数列 a = [a_0, ..., a_{n-1}] が与えられたとき，これらの中で k 番目に小さな要素を返す．

アルゴリズムはクイックソートに類似している．まず適当にピボットを選ぶ．次にピボットより小さい値と大きい値に要素を分類する．そしてそれぞれの集合の要素数から k 番目の要素がどちらの集合に入るかを判定して，再帰的に探索する．計算量は，ピボットをランダムに選んだとすると平均的に小さい値の集合と大きな値の集合は同じ程度のサイズとなるため，期待計算量の従う漸化式は T(n) = T(n/2) + O(n) であって，これを解くと T(n) = O(n) となる．

補足として，最悪計算量が O(n) になるものも存在する．それは数列を 5 個ずつの組に分解し，それぞれの中で中央値を求め，中央値のリストに対して再帰的に中央値を求めてそれをピボットに採用する．これによって全体の要素の 1/4 がピボット以下，1/4 がピボット以上であることが確定するので，要素数を判定して捨てられるほうを捨て，再帰的に探索する．このアルゴリズムの計算量は T(n) = T(n/5) + T(3n/4) + O(n) なので T(n) = O(n) である．しかしこのアルゴリズムは実装が複雑になるため，実用上は前述したクイックソートに類似したアルゴリズムのほうが高速である．

計算量

• 期待値の意味で O(n)．

ソースコード

int select(vector<int> &a, int k) {
  for (int l = 0, r = a.size()-1; l <= r; ) {
    int p = a[(l+r)/2];
    int i = l-1, j = r+1;
    while (1) {
      while (a[++i] < p);
      while (a[--j] > p);
      if (i >= j) break;
      swap(a[i], a[j]);
    }
    if (k == i-l) return a[i];
    else if (k < i-l) { r = i-1; }
    else if (k > i-l) { k -= (i-l+1); l = j+1; }
  }
  return -99999999; // k < 0 || k >= n
}

Verified