C++でバブルソートの問題であるAIZU ONLINE JUDGEのALDS_1_2_Dを解きました。


【目次】
問題
シェルソートを実装する




問題


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) は、一定の間隔 gg だけ離れた要素のみを対象とした挿入ソートである insertionSort(A, n, g) を、最初は大きい値から gg を狭めながら繰り返します。これをシェルソートと言います。

上の疑似コードの ? を埋めてこのプログラムを完成させてください。nn と数列 AA が与えられるので、疑似コード中の mm、mm 個の整数 Gi(i=0,1,...,m−1)Gi(i=0,1,...,m−1)、入力 AAを昇順にした列を出力するプログラムを作成してください。




シェルソートを実装する


ソートを行う間隔gは最後が1で終わればどんな数列でも良さそうだったので今回は、gn+1 = 3gn + 1という数列を使用します。

この数列に2のべき乗のような間隔が短すぎるものを入れると無駄な計算が発生しやすくなり、
シェルソートで実装する意味がなくなるみたいです。

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int cnt = 0;

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 = j - g;
cnt++;
}
A[j+g] = v;
}
}

void shellSort(int* A, int n){
cnt = 0;
int m = 1;
vector<int> G;
G.push_back(1);
while(3*G[m-1]+1 <= n){
G.push_back(3*G[m-1]+1);
m++;
}

cout << m << endl;
for(int i=G.size()-1;i>=0; --i){
cout << G[i];
if (i != 0){
cout << " ";
}
}
cout << endl;

for(int i = G.size()-1; i >= 0; --i){
insertionSort(A, n, G[i]);
}
}

int main(void){
int n;
cin >> n;
int *A = new int[n];
for(int i=0; i<n; ++i){
cin >> A[i];
}
shellSort(A, n);
cout << cnt << endl;
for(int i=0; i<n; ++i){
cout << A[i] << endl;
}

return 0;
}