Aizu Online Judge in C++ #ALDS1_2_D Shell Sort

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

・問題
　次のプログラムは、挿入ソートを応用して n 個の整数を含む数列 A を昇順に整列するプログラムです。

　shellSort(A, n) は、一定の間隔 g だけ離れた要素のみを対象とした挿入ソートである insertionSort(A, n, g) を、最初は大きい値から g を狭めながら繰り返します。これをシェルソートと言います。
　上の疑似コードの ? を埋めてこのプログラムを完成させてください。n と数列 A が与えられるので、疑似コード中の m、m 個の整数 Gi(i=0,1,...,m−1)、入力 A を昇順にした列を出力するプログラムを作成してください。
　ただし、出力は以下の条件を満 たす必要があります。

・入力される値
　1 行目に整数 n が与えられます。
　続く n 行目に n 個の整数 Ai(i=0,1,...,n−1) が与えられます。

・期待する出力
　1 行目に整数 m 、2 行目に m 個の整数 Gi(i=0,1,...,m−1) を空白区切りで出力してください。
　3 行目に、G を用いた場合のプログラムが終了した直後の cnt の値を出力してください。
　続く n 行に整列した Ai(i=0,1,...,n−1) を出力してください。
　この問題では、１つの入力に対して複数の解答があります。
　条件を満たす出力は全て正解となります。

・条件

僕が作成、提出したコードは、以下のとおりです。

/*
 ALDS1_2_D Shell Sort
 http://judge.u-aizu.ac.jp/
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<iostream>
#include<utility>
#include<cstdio>
using namespace std;
void InsertionSort(int a[],const int n,const int g,int *cnt){
    for(int i=g;i<n;++i){
        int tmp=a[i];
        int j=i-g;
        while(j>-1 && tmp<a[j]){
            a[j+g]=a[j];
            j=j-g;
            ++*cnt;
        }
        a[j+g]=tmp;
    }
}
void ShellSort(int a[], const int n){
    int cnt = 0;
    int m;
    int G[100];
    for(int i=0;i<100;++i){
        if(i==0){
            G[i]=n/2+1;
        }else{
            G[i]=G[i-1]/2-1;
        }
        if(G[i]<0){
            G[i-1]=1;
            G[i]=0;
            m=i;
            break;
        }
    }
    for(int i=0;i<m;++i){
        InsertionSort(a,n,G[i],&cnt);
    }
    printf("%d\n",m);
    for(int i=0;i<m;++i){
        if(i){
            putchar(' ');
        }
        printf("%d",G[i]);
    }
    printf("\n%d\n",cnt);
    for(int i=0;i<n;++i)
        printf("%d\n",a[i]);
}
int main(void){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;++i){
        scanf("%d",&a[i]);
    }
    ShellSort(a,n);
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_2_D Shell Sort