問題
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)
は、一定の間隔 だけ離れた要素を対象とした挿入ソートを、大きい値から小さい値に を変えながら行う。
うまく を選んで、以下の条件を満たすようにしてね。
制約
サンプル
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 に の決め方が載ってた。
最悪計算量を に抑えるには、数列の一般項を (ただし 以下) とすればいいらしい。
あとは漸化式を立てると となるので、これを追加していく。
コード
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; }