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