AOJ ALDS1 2_A（Bubble Sort）を解く

Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の2_A問題をC++で解いてみました。

ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#2「初等的ソート」では、考え方が分かりやすいソートアルゴリズムを学びます。

問題（2_A: Bubble Sort）

問題はリンク先をご覧ください。

AOJ ALDS1 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 の問題を紹介していきます。