Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の5_B問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#5「分割統治法」では、部分的な小さな問題を解くことによって、与えられた元の問題を解く手法を紹介します。
問題（5_B: Merge Sort）
問題はリンク先をご覧ください。
マージソートについて学びます。
マージソートについて
全体を2つに分割して、それぞれをソートして、その結果を小さな要素から取り出してソートした結果を得ます。分割は再帰的に行います。
計算量は、$O(N \log N)$ で高速に動きますが、別にメモリを確保する必要があります。
以下が擬似コードとなります。mergeSort を呼び出すと、再帰的に mergeSort が呼び出されて、最後に merge します。
merge(A, left, mid, right)
n1 = mid - left;
n2 = right - mid;
L[0...n1], R[0...n2] を生成
for i = 0 to n1-1
L[i] = A[left + i]
for i = 0 to n2-1
R[i] = A[mid + i]
L[n1] = INFTY
R[n2] = INFTY
i = 0
j = 0
for k = left to right-1
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
mergeSort(A, left, right)
if left+1 < right
mid = (left + right)/2;
mergeSort(A, left, mid)
mergeSort(A, mid, right)
merge(A, left, mid, right)マージソートの特徴は以下です。
- 計算量は、$O(N \log N)$
- 安定なソート（stable sort）
- 標準ライブラリ stable_sort では、マージソートで実装される場合が多い。
C++ プログラム例（ALDS1 5_B）
擬似コードをそのままC++にしています。門番に使う INFTY は、(1 << 30) としました（5行目）。
以下が、最終的なC++プログラムとなります。
#include <iostream>
#include <vector>
using namespace std;
#define INFTY (1 << 30)
vector<int> L;
vector<int> R;
int cnt = 0;
void merge(vector<int>& A, int left, int mid, int right)
{
int n1 = mid - left;
int n2 = right - mid;
for (int i = 0; i < n1; ++i) {
L[i] = A[left + i];
}
for (int i = 0; i < n2; ++i) {
R[i] = A[mid + i];
}
L[n1] = INFTY;
R[n2] = INFTY;
int i = 0;
int j = 0;
for (int k = left; k < right; ++k) {
++cnt;
if (L[i] <= R[j]) {
A[k] = L[i++];
} else {
A[k] = R[j++];
}
}
}
void mergeSort(vector<int>& A, int left, int right)
{
if (left + 1 < right) {
int mid = (left + right) / 2;
mergeSort(A, left, mid);
mergeSort(A, mid, right);
merge(A, left, mid, right);
}
}
int main()
{
int n;
cin >> n;
vector<int> s(n);
L.assign(n / 2 + 2, 0);
R.assign(n / 2 + 2, 0);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
mergeSort(s, 0, n);
for (int i = 0; i < n; ++i) {
cout << s[i] << " \n"[i == n - 1];
}
cout << cnt << endl;
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
計算量 $O(N^2)$ の挿入ソート/バブルソート/選択ソートを紹介しました。マージソートは、計算量 $O(N \log N)$ でソートできます。分割して計算を行う威力が分かります。
引き続き、ALDS1 の問題を紹介していきます。
