Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の1_A問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#1「入門」は、このコースの導入となっています。
問題（1_A: Insertion Sort）
問題はリンク先をご覧ください。
AOJ ALDS1 1_A問題: Insertion Sort
挿入ソートについて学びます。
ソートと挿入ソートについて
ソートは、プログラミング言語が持っているライブラリを通じて使うことが多いと思います。しかし、ソートは、多くのアルゴリズムの定番教科書で章を設けて解説されていて、学びが多いアイテムだと考えられています。
ALDS1 では、トピック#2と#6でソートについて集中的に学びます。
コースの導入として、実装が簡単なソートアルゴリズム「挿入ソート」を学びます。「挿入ソート」は、左から右に小さい順に並ぶように値を入れ替えていきます。問題に紹介されている以下の擬似コードで実現できます。
insertionSort(A, N) // N個の要素を含む0-オリジンの配列A
for i が 1 から N-1 まで
v = A[i]
j = i - 1
while j >= 0 かつ A[j] > v
A[j+1] = A[j]
--j
A[j+1] = v挿入ソートの特徴は以下です。
- 計算量は、$O(N^2)$
- 安定なソート（stable sort）
- もともとソートされているデータに対しては、N-1回しか比較しない。
ある程度整列されたデータに対しては、計算量が少ない。
C++ プログラム例（ALDS1 1_A）
問題で与えられる数列を挿入ソートを用いてソートします。数列の初期状態とアルゴリズムの各 $i$ の処理が終了した時点での数列並びを出力します。
C++ でコーディングしたため、配列ではなく vector コンテナを使いました。このため、擬似コードにあった $N$ は引数として渡していません。これは vector コンテナでは要素数を size() メソッドで取得できるからです。
以下の3関数から成ります。
- 関数 print_vector : 引数で与えらえた vector コンテナの要素を空白区切りで出力します。
- 要素の後の空白と改行を、文字列 ” \n” （空白と改行コードの2文字）と添え字の演算子 (i == a.size() – 1) の値が 0 か 1 となることを用いて出力しています。多少読みにくいですが、1行で書けるため、この書き方を使っています。
- 関数 insertionSort : 擬似コードをそのままコードにしました。
- 関数 main : 要素数 $N$ と数列 $A$ を読み込み、数列の初期状態を出力して、insertionSort を呼び出します。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
using namespace std;
void print_vector(vector<int> a)
{
for (int i = 0; i < a.size(); ++i) {
cout << a[i] << " \n"[i == a.size() - 1];
}
}
void insertionSort(vector<int>& a)
{
for (int i = 1; i < a.size(); ++i) {
int v = a[i];
int j = i - 1;
while ((j >= 0)&&(a[j] > v)) {
a[j + 1] = a[j];
--j;
}
a[j + 1] = v;
print_vector(a);
}
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
print_vector(a);
insertionSort(a);
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
「プログラミング入門」（ITP1）と「プログラミング応用」（ITP2）をすべて解くことができました（まとめ記事のリンクを貼りました）。続いて、ALDS1 を解くことにしました。
ALDS1 は、かなり難しい問題も含まれていました。このコースを通じてアルゴリズムを体系的に学びたいと思います。
引き続き、ALDS1 の問題を紹介していきます。
