AOJ ALDS1 2_B（Selection Sort）を解く

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

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

問題（2_B: Selection Sort）

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

AOJ ALDS1 2_B問題: Selection Sort

選択ソートについて学びます。

選択ソートについて

「残りの範囲から一番小さい値を選択する」ことを繰り返してソートします。最初は全範囲を対象として、1要素ずつ範囲を小さくしていきます。問題に紹介されている以下の擬似コードで実現できます。

selectionSort(A, N) // N個の要素を含む0-オリジンの配列A
    for i が 0 から N-1 まで
        minj = i
        for j が i から N-1 まで
            if A[j] < A[minj]
            minj = j
        A[i] と A[minj] を交換

選択ソートの特徴は以下です。

• 計算量は、$O(N^2)$
• 離れた場所の要素を入れ替えるため安定なソートではない（unstable sort）
• 段階的に一番小さい要素を選ぶという考え方は分かりやすい。

C++ プログラム例（ALDS1 2_B）

問題で与えられる数列を選択ソートを用いてソートします。ソート後の文字列と交換した回数（関数 swap の呼び出し回数）を出力します。

プログラムのベースは、ALDS1 1_A（挿入ソート）を流用してます。

C++ でコーディングしたため、配列ではなく vector コンテナを使いました。このため、擬似コードにあった $N$ は引数として渡していません。これは vector コンテナでは要素数を size() メソッドで取得できるからです。

以下の3関数から成ります。

• 関数 print_vector : 引数で与えらえた vector コンテナの要素を空白区切りで出力します。
  • 要素の後の空白と改行を、文字列 ” \n” （空白と改行コードの2文字）と添え字の演算子 (i == a.size() – 1) の値が 0 か 1 となることを用いて出力しています。多少読みにくいですが、1行で書けるため、この書き方を使っています。
• 関数 selectionSort : 擬似コードをそのままコードにしました。swap した回数を返しています。
• 関数 main : 要素数 $N$ と数列 $A$ を読み込み、selectionSort を呼び出します。

以下が、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 selectionSort(vector<int>& a)
{
	int n_swap = 0;

	for (int i = 0; i < a.size(); ++i) {
		int minj = i;
		for (int j = i; j < a.size(); ++j) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		if (i != minj) {
			swap(a[i], a[minj]);
			++n_swap;
		}
	}

	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 =  selectionSort(a);
	print_vector(a);
	cout << n_swap << endl;

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

挿入ソート、バブルソートに続き、選択ソートを学びました。選択ソートは前の2つのソートアルゴリズムと異なり安定ではありません。

選択ソートは速いとは言えませんが、分かりやすい考え方のアルゴリズムです。

引き続き、ALDS1 の問題を紹介していきます。