うめすこんぶ

日々のプログラミングで残しておきたいメモ.何かの役に立てれば幸いです.

配列中でk番目に小さい要素を見つける,O(N)の関数

スポンサーリンク

珠玉のプログラミングの問題をやってます. コラム11の問題のなかで,「配列中でk番目に小さい要素を見つける関数で,O(N)のものを 作れ」というのがあったので解いてみました.

結構悩んだんですけど,要はクイックソートを片側のみ行うようにすれば解けます. 処理としては,とりあえずクイックソートを行って配列を分割.小さい方の部分配列の数が kより小さかったら,k番目に小さいものは大きいのほうの部分配列に在ります.逆に,小さい方の部分配列の数がkより大きかったら,k番目に小さいものはその配列中に在るはずです. よって,あとは目的の要素があると思われる部分配列だけまたクイックソートの分割をすればいい,ということになりますので,計算量はクイックソートよりずっと落ちます. どのぐらいになるかというと,最初がn個の分割,次が平均で1/2 * n個の部分配列の分割,その次が1/2 * 1/2 * nの部分配列の分割…とやっていくと,

n + 1/2 * n + 1/4 * n + ... < 2n

となるので,計算回数はO(n)で達成できます.しかし,最悪の場合はO(n2)かかりますね.

ソース

javascriptで書いてます.

/**
 * k番目に小さい数値を見つける
 * @param x 配列
 * @param k 指定順位
 */
function searchLankK(x, k) {
  /**
   * 片側のみのクイックソート
   * @param l ソート範囲の最小インデックス
   * @param u ソート範囲の最大インデックス
   * @param k 指定順位
   */
  function selectOne(l, u, k) {
    if (l >= u) return;
    
    var t = x[l], m = l;        /* tはピボット,mは境界*/
    /* ピボットを元に並べ替え */
    for (var i = l + 1; i <= u; i++) {
      if (x[i] < t) {
        var temp = x[i];        /* swap */
        x[i] = x[++m];
        x[m] = temp;
      }
    }
    
    var temp = x[m];            /* swap */
    x[m] = x[l];
    x[l] = temp;

    /* ピボットより小さい要素がk個に収まるかを見る*/
    if (m < k) {
      /* k番目はピボットより大きい範囲に在る */
      selectOne(m + 1, u, k);
    }
    else if (m > k) {
      /* k番目はピボットより小さい範囲に在る */
      selectOne(l, m, k);
    }                           /* m == kならなにもしない */
  }
  k--;   /* 配列は0から始めるので,kをそれに合わせる */
  selectOne(0, x.length-1, k); /* 配列全体についてselectOne実行 */
  return x[k];                 /* k番目の値を返す */
}

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造