Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の2_C問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#2「初等的ソート」では、考え方が分かりやすいソートアルゴリズムを学びます。
問題（2_C: Stable Sort）
問題はリンク先をご覧ください。
ある型の変数にソートを適用する例とソートの安定性について紹介します。
ソートの安定性について
ソートアルゴリズムで同じデータが複数ある場合に出力が、入力に出現する順序で出力される場合に、そのソートアルゴリズムは「安定である」と呼びます。挿入ソートとバブルソートは安定なソートです。選択ソートは安定なソートではありません。
C++ プログラム例（ALDS1 2_C）
トランプのカードを表す文字列が与えられます。そのカードを数字（文字列の2文字目）を基準にソートします。ソートは、2_A で学んだバブルソートと 2_B で学んだ選択ソートを使います。
以下が今回のプログラムのポイントです。
- 関数 bubbleSort は、戻り値を戻す必要がなくなりました。カードの数字を比較するように20行目を変更しました。
- 関数 selectionSort は、戻り値を戻す必要がなくなりました。カードの数字を比較するように35行目を変更しました。
- バブルソートの結果は安定となるため、常に “Stable” を出力します（60行目）。
- 選択ソートの結果は、バブルソートの結果と比較して、一致していれば “Stable” を、一致していなければ “Not Stable” を出力します（64ー68行目）。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
#include <algorithm> // swap C++03
#include <utility> // swap C++11 or later
using namespace std;
void print_vector(vector<string> a)
{
for (int i = 0; i < a.size(); ++i) {
cout << a[i] << " \n"[i == a.size() - 1];
}
}
void bubbleSort(vector<string>& a)
{
bool flag = true;
while (flag) {
flag = false;
for (int j = a.size() - 1; j >= 1; --j) {
if (a[j][1] < a[j - 1][1]) {
swap(a[j], a[j - 1]);
flag = true;
}
}
}
return n_swap;
}
void selectionSort(vector<int>& a)
{
for (int i = 0; i < a.size(); ++i) {
int minj = i;
for (int j = i; j < a.size(); ++j) {
if (a[j][1] < a[minj][1]) {
minj = j;
}
}
if (i != minj) {
swap(a[i], a[minj]);
}
}
return n_swap;
}
int main()
{
int n;
cin >> n;
vector<string> a(n), bubble(n), selection(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
bubble = a;
selection = a;
bubbleSort(bubble);
print_vector(bubble);
cout << "Stable" << endl;
selectionSort(selection);
print_vector(selection);
if (bubble == selection) {
cout << "Stable" << endl;
} else {
cout << "Not stable" << endl;
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
今回の問題は、文字列の2文字目に従ってソートしました。すでに学んだバブルソート、選択ソートのプログラムを修正しました。
ソートの安定性は、計算機のパワーが大きくなってきたため、昔ほどは気にならなくなってきました（並べ直せばよいので）。アルゴリズムの教科書では、定番として紹介されています。
引き続き、ALDS1 の問題を紹介していきます。
