Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の6_C問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#6「ソート」では、実用的なソートアルゴリズムについて紹介します。
問題（6_C: Quick Sort）
問題はリンク先をご覧ください。
クイックソートについて学びます。
クイックソートについて
全体を2つに分割して、それぞれをソートします。分割は再帰的に行います。この考え方は、マージソートと同じです。ただし、外部メモリを必要とせず、与えられた配列内で入れ替えをします（partition）。このため、離れた要素を入れ替える場合があり、安定なソートではなくなります。
以下の擬似コードを実装します。関数 partition は、6_B問題で紹介済です。
partition(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
if A[j] <= x
i = i+1
A[i] と A[j] を交換
A[i+1] と A[r] を交換
return i+1
quicksort(A, p, r)
if p < r
q = partition(A, p, r)
quickSort(A, p, q-1)
quickSort(A, q+1, r)クイックソートの特徴は以下です。
- 平均の計算量は、$O(N \log N)$、ただし、上述の擬似コードの場合、データの並びによっては、計算量が $O(N^2)$ となることがあります。これを避けるためには、基準（A[r]）を中央値に近い値を選ぶなどの工夫をします。
- 関数 partition で離れた位置の要素を入れ替えるため、安定なソートではない。
- マージソートとは異なり外部メモリを必要としない。
C++ プログラム例（ALDS1 6_C）
上で説明した擬似コードをそのままC++として書き換えました（45ー67、88行目）。
結果が安定なソートとなっているかマージソートの結果と比較します。マージソートは、5_B問題で紹介したプログラムを流用しました（6ー43、84ー86行目）。
問題文で示されている擬似コードに合わせたため、マージソートでは、[0, n) を渡しています。一方、クイックソートでは、[0, n-1] を渡しています。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INFTY (1 << 30)
vector<pair<char, int>> L;
vector<pair<char, int>> R;
int cnt = 0;
void merge(vector<pair<char, 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] = make_pair(' ', INFTY);
R[n2] = make_pair(' ', INFTY);
int i = 0;
int j = 0;
for (int k = left; k < right; ++k) {
++cnt;
if (L[i].second <= R[j].second) {
a[k] = L[i++];
} else {
a[k] = R[j++];
}
}
}
void mergeSort(vector<pair<char, 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 partition(vector<pair<char, int>>& a, int p, int r)
{
int x = a[r].second;
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j].second <= x) {
++i;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
void quickSort(vector<pair<char, int>>& a, int p, int r)
{
if (p < r) {
int q = partition(a, p, r);
quickSort(a, p, q - 1);
quickSort(a, q + 1, r);
}
}
int main()
{
int n;
cin >> n;
vector<pair<char, int>> a(n);
for (int i = 0; i < n; ++i) {
char c;
int number;
cin >> c >> number;
a[i] = make_pair(c, number);
}
vector<pair<char, int>> b(n);
b = a;
L.assign(n / 2 + 2, make_pair(' ', 0));
R.assign(n / 2 + 2, make_pair(' ', 0));
mergeSort(b, 0, n);
quickSort(a, 0, n - 1);
bool stable = true;
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
stable = false;
}
}
if (stable) {
cout << "Stable" << endl;
} else {
cout << "Not stable" << endl;
}
for (int i = 0; i < n; ++i) {
cout << a[i].first << " " << a[i].second << endl;
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
C++標準ライブラリでは、特定のアルゴリズムを指定していませんが、計算量を指定しています。このため、以下のような実装が多いようです（cpprefjp 様の記述を引用させていただきました。）。
- sort: クイックソートの改良版であるイントロソートが使われることが多い
イントロソートでは、クイックソートとヒープソートを組み合わせる。 - stable_sort: 一般的なマージソートで実装される。
引き続き、ALDS1 の問題を紹介していきます。
