Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の6_B問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#6「ソート」では、実用的なソートアルゴリズムについて紹介します。
問題（6_B: Partition）
問題はリンク先をご覧ください。
クイックソートの下請け関数を準備します。
関数 parittion
以下の擬似コードを実装します。
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関数 partition は、以下のように動きます。
- 配列 A[p … r] を以下に分割する。ここで、A[q] = A[r] としておく。
- A[p … q − 1] の各要素が A[q] 以下
- A[q+1 … r] の各要素が A[q] より大きい
- インデックス q を戻り値として返す。
C++ プログラム例（ALDS1 6_B）
擬似コードをそのままC++として書き換えました。配列ではなく Vector コンテナとして実装しました。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int partition(vector<int>& a, int p, int r)
{
int x = a[r];
int i = p - 1;
for (int j = p; j < r; ++j) {
if (a[j] <= x) {
++i;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int q = partition(a, 0, n - 1);
for (int i = 0; i < n; ++i) {
if (i != q) {
cout << a[i] << " \n"[i == n - 1];
} else {
cout << "[" << a[i] << "]" << " \n"[i == n - 1];
}
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
次の 6_C問題でクイックソートを実装します。その下請け関数を紹介しました。
引き続き、ALDS1 の問題を紹介していきます。
