Aizu Online Judge(AOJ)が提供している「アルゴリズムとデータ構造入門」(ALDS1)の2_A問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#2「初等的ソート」では、考え方が分かりやすいソートアルゴリズムを学びます。
問題(2_A: Bubble Sort)
問題はリンク先をご覧ください。
バブルソートについて学びます。
バブルソートについて
「隣り合った要素の大きさが逆転していれば入れ替える」ことを繰り返してソートします。入れ替える要素がなければソートは終了です。問題に紹介されている以下の擬似コードで実現できます。
bubbleSort(A, N) // N 個の要素を含む 0-オリジンの配列 A
flag = 1 // 逆の隣接要素が存在する
while flag
flag = 0
for j が N-1 から 1 まで
if A[j] < A[j-1]
A[j] と A[j-1] を交換
flag = 1
バブルソートの特徴は以下です。
- 計算量は、$O(N^2)$
- 安定なソート(stable sort)
- 差がひとつの要素を繰り返して入れ替えるため遅い場合が多い。
C++ プログラム例(ALDS1 2_A)
問題で与えられる数列をバブルソートを用いてソートします。ソート後の文字列と交換した回数(関数 swap の呼び出し回数)を出力します。
プログラムのベースは、ALDS1 1_A(挿入ソート)を流用してます。
C++ でコーディングしたため、配列ではなく vector コンテナを使いました。このため、擬似コードにあった $N$ は引数として渡していません。これは vector コンテナでは要素数を size() メソッドで取得できるからです。
以下の3関数から成ります。
- 関数 print_vector : 引数で与えらえた vector コンテナの要素を空白区切りで出力します。
- 要素の後の空白と改行を、文字列 ” \n” (空白と改行コードの2文字)と添え字の演算子 (i == a.size() – 1) の値が 0 か 1 となることを用いて出力しています。多少読みにくいですが、1行で書けるため、この書き方を使っています。
- 関数 bubbleSort : 擬似コードをそのままコードにしました。swap した回数を返しています。
- 関数 main : 要素数 $N$ と数列 $A$ を読み込み、bubbleSort を呼び出します。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
#include <algorithm> // swap C++03
#include <utility> // swap C++11 or later
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];
}
}
int bubbleSort(vector<int>& a)
{
int n_swap = 0;
bool flag = true;
while (flag) {
flag = false;
for (int j = a.size() - 1; j >= 1; --j) {
if (a[j] < a[j - 1]) {
swap(a[j], a[j - 1]);
++n_swap;
flag = true;
}
}
}
return n_swap;
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int n_swap = bubbleSort(a);
print_vector(a);
cout << n_swap << endl;
return 0;
}
上記プログラムは、AOJ で「AC(Accepted=正解)」と判定されました。
最後に
挿入ソートに続き、バブルソートを学びました。バブルソートは速いとは言えませんが、「隣あった要素の大きさが逆転していれば入れ替える」という素朴な方法でソートします。
バブルソートは実践的な場では使われませんが、このアルゴリズムで swap する回数は、反転数と呼ばれていて、競技プログラミングの題材として扱われる場合があります。反転数の計算量は、素朴な方法では $O(N^2)$ となります。セグメント木などを使えば $O(N \log N)$ の計算量で求めることができます。
引き続き、ALDS1 の問題を紹介していきます。