C++で実装する初等的ソートアルゴリズム４【シェルソート】

初等的ソートアルゴリズム第4弾。今回はシェルソートを実装してみます。挿入ソートの応用です。
挿入ソートがわからない方はこちら↓
programgenjin.hatenablog.com

目標

シェルソートを理解する。例によって問題を解きます。

シェルソート

あらかじめある程度ソートしてあれば高速にソートできるという挿入ソートの性質を利用したソーティングアルゴリズム。
まず荒くソートして、だんだん細かくソートしていく。

アルゴリズム

1. 以下の処理を、 $g$ （ $g>1$ ）の値を小さくしながら繰り返す：
1. 一定間隔 $g$ だけ離れた要素のみを対象とする挿入ソートを行う。
2. $g = 1$ として挿入ソートを行う。

計算量を減らすには $g$ の値をうまく選ぶ必要がある。例えば、 $\{g_i\}_{i=0, 1, 2, \dots} = 1, 4, 13, \dots$ （ $g_{n+1} = 3 g_n + 1$ ）の時、 $O(N^{1.25})$ と予想されている。

問題を解く

以下の問題をときました。言語はC++です。
Shell Sort | Aizu Online Judge

#include<iostream>
#include<vector>
using namespace std;

long long cnt;

// 一定間隔g離れた要素のみを対象とした選択ソート
void insertion_sort(int seq[], int n, int g) {
  int i, j, v;
  for (i = g; i < n; i++) {
    v = seq[i];
    j = i - g;
    while (j >= 0 && seq[j] > v) {
      seq[j+g] = seq[j];
      j -= g;
      cnt++;
    }
    seq[j+g] = v;
  }
}

//  シェルソート
void shell_sort(int seq[], vector<int> G, int n, int m) {
  int i, g;
  
  for (i = m-1; i >= 0; i--) {
    g = G[i];
    insertion_sort(seq, n, g);
  }    
}

int main() {
  int i, n, m, g;
  int seq[1000000];
  vector<int> G;
  
  cin >> n;
  for (i = 0; i < n; i++) cin >> seq[i];
  
  // gたちを決める
  g = 1;
  while (g <= n) {
    G.push_back(g);
    g = 3 * g + 1;
  }
  m = G.size();

  // sort
  shell_sort(seq, G, n, m);

  // ourput
  cout << m << endl;
  for (i = m-1; i >= 0; i--) {
    if (i < m - 1) cout << " ";
    cout << G[i];
  }
  cout << endl;
  cout << cnt << endl;
  for (i = 0; i < n; i++) cout << seq[i] << endl;
  
  return 0;
}