D - Shell Sort

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_D (新しいタブで開く)

問題文

シェルソート。挿入ソートの応用版。
疑似コードは以下の通り。

insertionSort(A, n, g)
    for i = g to n-1
        v = A[i]
        j = i - g
        while j >= 0 && A[j] > v
            A[j+g] = A[j]
            j = j - g
            cnt++
        A[j+g] = v

shellSort(A, n)
    cnt = 0
    m = ?
    G[] = {?, ?,..., ?}
    for i = 0 to m-1
        insertionSort(A, n, G[i])

shellSort(A, n) は、一定の間隔 $g$ だけ離れた要素を対象とした挿入ソートを、大きい値から小さい値に $g$ を変えながら行う。

うまく $g$ を選んで、以下の条件を満たすようにしてね。

• $1 \le m \le 100$
• $0 \le G_i \le n$
• $cnt \le \lceil n^{1.5} \rceil$

制約

• $1 \le n \le 10^6$
• $0 \le A_i \le 10^9$

サンプル

I/O 1

5
5
1
4
3
2

2
4 1
3
1
2
3
4
5

I/O 2

3
3
2
1

1
1
3
1
2
3

考察

シェルソート - Wikipedia (新しいタブで開く) に $g$ の決め方が載ってた。

最悪計算量を $O(n^{1.5})$ に抑えるには、数列の一般項を $\frac{3^k - 1}{2}$ (ただし $\lceil \frac{n}{3} \rceil$ 以下) とすればいいらしい。
あとは漸化式を立てると $g_{next} = 3 \times g_{now} + 1$ となるので、これを追加していく。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_2_D/judge/6745933/C++17 (新しいタブで開く)

int cnt = 0;

void InsertionSort(vector<int>& a, int n, int g) {
  for (int i = g; i < n; i++) {
    Debug(g, i, n);
    int v = a[i];
    int j = i - g;
    while (j >= 0 && a[j] > v) {
      Debug(j + g);
      a[j + g] = a[j];
      j = j - g;
      cnt++;
    }
    a[j + g] = v;
  }
}

void ShellSort(vector<int>& a, int n) {
  vector<int> g(0);
  int now = 1;
  while (now <= n) {
    g.push_back(now);
    now = 3 * now + 1;
  }
  sort(g.rbegin(), g.rend());
  int m = g.size();
  cout << m << endl;
  rep(i, m) cout << g[i] << (i == m - 1 ? "\n" : " ");
  rep(i, m) InsertionSort(a, n, g[i]);
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  ShellSort(a, n);
  cout << cnt << endl;
  for (int x : a) cout << x << endl;
  return 0;
}