ALDS1_2_D シェルソートをC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

AIZU ONLINE JUDGEの「ALDS1_2_D Shell Sort」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文
解答
感想
まとめ

問題文

次のプログラムは、挿入ソートを応用して n 個の整数を含む数列 A を昇順に整列するプログラムです。
1 insertionSort(A, n, g)
2 for i = g to n-1
3 v = A[i]
4 j = i - g
5 while j >= 0 && A[j] > v
6 A[j+g] = A[j]
7 j = j - g
8 cnt++
9 A[j+g] = v
10
11 shellSort(A, n)
12 cnt = 0
13 m = ?
14 G[] = {?, ?,..., ?}
15 for i = 0 to m-1
16 insertionSort(A, n, G[i])
shellSort(A, n) は、一定の間隔 g だけ離れた要素のみを対象とした挿入ソートである insertionSort(A, n, g) を、最初は大きい値から g を狭めながら繰り返します。これをシェルソートと言います。
上の疑似コードの ? を埋めてこのプログラムを完成させてください。n と数列 A が与えられるので、疑似コード中の m、m 個の整数 Gi(i=0,1,…,m−1)、入力 Aを昇順にした列を出力するプログラムを作成してください。ただし、出力は以下の条件を満たす必要があります。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_D

解答

#include <bits/stdc++.h>
using namespace std;

void print(int a[], int n, int *cnt, vector<int> g) {
    cout << g.size() << endl;
    for(int i = g.size() - 1; i >= 0; i--) {
        cout << g[i] << (i == 0 ? '\n' : ' ');
    }
    cout << *cnt << endl;
    for(int i = 0; i < n; i++) {
        cout << a[i] << endl;
    }
}

void insertion_sort(int a[], int n, int h, int *cnt) {
    for(int i = h; i < n; i++) {
        int v = a[i];
        int j = i - h;
        while(j >= 0 && a[j] > v) {
            a[j + h] = a[j];
            j -= h;
            ++*cnt;
        }
        a[j + h] = v;
    }
}

void shell_sort(int a[], int n, int *cnt, vector<int> g) {
    *cnt = 0;
    int x = 1;
    while(x <= n) {
        g.push_back(x);
        x = 3 * x + 1;
    }
    int m = g.size();
    for(int i = m - 1; i >= 0; i--) {
        insertion_sort(a, n, g[i], cnt);
    }
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = 0;
    vector<int> g;
    // print(a, n, &cnt);
    // insertion_sort(a, n, 1, &cnt);
    shell_sort(a, n, &cnt, g);
    print(a, n, &cnt, g);
    return 0;
}