Spaghetti Source logo

バブルソートの交換回数

説明

mergecount は数列 a = [a_0, ..., a_{n-1}] をバブルソートするときの要素の交換回数を求める.

バブルソートの交換回数は,各要素 a[k] について,それより左側にある要素のうち a[k] より大きなものの数を c[k] とすれば Σ c[k] で与えられる.重要なのは,この値はどこから計算しても構わないということである.すなわち計算に構造を持たせることで,本当にバブルソートを行うよりも高速に計算することができる.

具体的なアルゴリズムはマージソートに類似している.まずリストを真ん中で分割し,左右それぞれをソートするための交換回数を再帰的に求める.このとき同時に数列はソートしておく.次にこれら二つの列をマージするときの交換回数を求める.具体的には右側の要素から要素を取り出すときの交換回数は,既に埋まった要素の個数から計算できる.

計算量

ソースコード

int mergecount(vector<int> &a) {
  int count = 0;
  int n = a.size();
  if (n > 1) {
    vector<int> b(a.begin(), a.begin() + n/2);
    vector<int> c(a.begin() + n/2, a.end());
    count += mergecount(b);
    count += mergecount(c);
    for (int i = 0, j = 0, k = 0; i < n; ++i)
      if (k == c.size())       a[i] = b[j++];
      else if (j == b.size())  a[i] = c[k++];
      else if (b[j] <= c[k])   a[i] = b[j++];
      else                   { a[i] = c[k++]; count += n/2 - j; }
  }
  return count;
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2006.12.26 03:41:55.