[알고리즘] 쉘 정렬 (shell sort)

쉘 정렬은 어느 정도 정렬된 배열을 굉장히 빠르게 정렬하는 알고리즘 입니다.
셀 정렬은 일정한 간격 g만큼 떨어진 요소만을 대상으로 삽입 정렬을 반복합니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

long long cnt;
int l;
int A[100000];
int n;
vector<int>G;

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

void shellSort(int A[], int n) {
    for(int h = 1; ;) {
        if(h > n) break;
        G.push_back(h);
        h = 3*h + 1;
    }
    for(int i = G.size() - 1; i >= 0; i--) {
        insertionSort(A, n, G[i]);
    }
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &A[i]);
    cnt = 0;
    shellSort(A, n);
    cout << G.size() << endl;
    for(int i = G.size() -1; i >=0; i--) {
        printf("%d", G[i]);
        if(i) printf(" ");
    }
    printf("\n");
    printf("%lld\n", cnt);
    for(int i = 0; i < n; i++) printf("%d\n", A[i]);
    return 0;
}