はじめに
ソートアルゴリズムの実装は代入/比較/繰り返しなど、プログラミングを学ぶ上での基本がきっちり詰まっていて、ビギナーのトレーニングには格好の題材です。簡単なソートアルゴリズムの代表格といえばバブルソートと選択ソートでしょうか。
この記事では、選択ソートアルゴリズムを「STL」（C++の標準テンプレートライブラリ；Standard Template Library）で実装し、インテルが公開しているマルチコアCPU向けのC++テンプレートライブラリ「インテル スレッディング・ビルディング・ブロック」（インテルTBB）を使ってマルチスレッドによる高速化を試みます。
選択ソートのSTLによる実装
選択ソート（selection sort）のアルゴリズムはバブルソート以上に単純です。配列 data[N] を昇順にソートするには
data[i]～data[N-1]の中から最も小さい要素を探し、 それとdata[i]とを交換する
を i = 0～N-1 に対してくり返すだけ。data[0]～data[N-1]中の最小要素とdata[0]とを交換すれば、当然data[0]が最小となります。次に（data[0]を除いた）data[1]～data[N-1]中の最小要素をdata[1]と交換するのでdata[1]は2番目に小さい要素となります。以下この操作を繰り返せばソート完了という次第。
STLの<algorithm>には最も小さい要素（を指すイテレータ）を返すmin_element、および2つの要素をイテレータを介して交換するiter_swapがありますから、選択ソートの実装はきわめて簡単です。
// 選択ソート
template<typename Iterator>
void selection_sort(Iterator first, Iterator last) {
while ( first != last ) {
// [first,last)中の最小要素をfirstと交換
std::iter_swap(first, std::min_element(first,last));
++first;
}
}
10行足らずで書けてしまう選択ソート、性能はいかがなものでしょう。お試しに文字列の並び、vector<string> をソートしましょうか。前準備としてソートアルゴリズムを関数オブジェクトに仕立てておきます。
class sort_base {
public:
typedef std::vector<std::string>::iterator iterator;
protected:
iterator first_;
iterator last_;
virtual void do_sort() const =0; // ←導出クラスではコレを再定義して処理を書く
public:
sort_base(iterator first, iterator last) : first_(first), last_(last) {}
void operator()() const {
do_sort(); // ソートして...
// 昇順に並んでいることを確認
assert( std::adjacent_find(first_, last_, std::greater<std::string>()) == last_ );
}
};
/*
* 至極真っ当な選択ソート
*/
class normal_sort : public sort_base {
public:
normal_sort(iterator first, iterator last) : sort_base(first,last) {}
protected:
virtual void do_sort() const {
selection_sort(first_, last_);
}
};
// 関数オブジェクトを評価(実行)し、処理時間を測定する
void execute(const sort_base& sort_fn) {
tbb::tick_count start = tbb::tick_count::now();
sort_fn();
std::cout << (tbb::tick_count::now() - start).seconds() << " [sec]\n";
}
int main() {
std::vector<std::string> source;
std::vector<std::string> input;
{ // ソート対象を生成。
// A..Hの順列(8!個)を用意し、
std::string value = "ABCDEFGH";
do { source.push_back(value);
} while ( std::next_permutation(value.begin(), value.end()) );
// その順序をかき混ぜる。
std::random_shuffle(source.begin(),source.end());
}
{ // フツーに選択ソート
input = source;
std::cout << "normal_sort ....... " << std::flush;
execute(normal_sort(input.begin(), input.end()));
}
}
