Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の2_D問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#2「初等的ソート」では、考え方が分かりやすいソートアルゴリズムを学びます。
問題（2_D: Stable Sort）
問題はリンク先をご覧ください。
シェルソートについて学びます。
シェルソートについて
シェルソートは、1_Aで学んだ挿入ソートの入れ替える間隔を大きい数字から選択して、徐々に小さくしていき、最終的に入れ替える間隔を1にしたアルゴリズムです。入れ替える間隔が1である操作は挿入ソートと同じです。
問題には、以下の擬似コードが紹介されています。配列 g が間隔となり、m がその配列の大きさとなります。
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)
m = ?
g[] = {?, ?,..., ?}
for i = 0 to m-1
insertionSort(A, n, g[i])シェルソートの特徴は以下です。Wikipedia の記事（英語版）を参考にしました。
- 計算量は、数列 g（gap sequence） に依存する。
- 1, 4, 13, 40, 121, 3m + 1, … は、$O(n^{1.5})$
- 1, 8, 23, 77, 281, 4m + 3 2m-1 + 1 … は、$O(n^{1.33..})$
- $O(n \log n)$ となる数列があるかは未解決問題となっている。
- 離れた場所の要素を入れ替えるため安定なソートではない（unstable sort）
C++ プログラム例（ALDS1 2_D）
問題で与えられる数列をシェルソートを用いてソートします。ギャップ数列の個数とその要素、擬似コードにある cnt、ソート後の文字列を出力します。
数列 g は、このコースの書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」（渡部有隆著 マイナビ出版2015年）で採用していた
1, 4, 13, 40, 121, 3m + 1, …
としました。擬似コードをそのままC++にしています。以下が、最終的なC++プログラムとなります。
#include <iostream>
#include <vector>
using namespace std;
int cnt;
void insertionSort(vector<int>& a, int g)
{
for (int i = g; i < a.size(); ++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;
}
}
vector<int> shellSort(vector<int>& a)
{
cnt = 0;
vector<int> g;
int m = 0;
while (true) {
m = 3 * m + 1;
if (m > a.size()) {
break;
}
g.push_back(m);
}
for (int i = g.size() - 1; i >= 0; --i) {
insertionSort(a, g[i]);
}
return g;
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> g = shellSort(a);
cout << g.size() << endl;
for (int i = g.size() - 1; i >= 0; --i) {
cout << g[i] << " \n"[i == 0];
}
cout << cnt << endl;
for (int i = 0; i < n; ++i) {
cout << a[i] << endl;
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
トピック#2では、バブルソート、選択ソート、シェルソート（挿入ソートの応用）を紹介しました。すべてソートの根拠が分かりやすいアルゴリズムでした。トピック#5、トピック#6で効率が良いソートアルゴリズムを紹介します。
引き続き、ALDS1 の問題を紹介していきます。
