D - Shell Sort

cpaojalds1

最終更新日

Table of Contents

Loading...

問題

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) は、一定の間隔 gg だけ離れた要素を対象とした挿入ソートを、大きい値から小さい値に gg を変えながら行う。

うまく gg を選んで、以下の条件を満たすようにしてね。

制約

サンプル

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 (新しいタブで開く)gg の決め方が載ってた。

最悪計算量を O(n1.5)O(n^{1.5}) に抑えるには、数列の一般項を 3k12\frac{3^k - 1}{2} (ただし n3\lceil \frac{n}{3} \rceil 以下) とすればいいらしい。
あとは漸化式を立てると gnext=3×gnow+1g_{next} = 3 \times g_{now} + 1 となるので、これを追加していく。

コード

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; }