STL コンテナを代入できる選択ソートテンプレート関数

概要

STL のソート関数テンプレートは非常に便利だが、この関数を適用するためにはコンテナにランダムアクセスイテレータが定義されている必要がある。

そのため、 std::list など、ランダムアクセスイテレータが使えないコンテナについては自前でソート関数を書く必要がある。

そこで、 Wikipedia の記事を参考にして選択ソートのテンプレート関数を書いた。計算量 O(n^2) だが Bubble sort よりは早い。

アルゴリズム

Wikipedia より引用

データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す（厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後（残り）は必ず最大値になるからである）。大小が入れ替わる降順の場合も同様の手法。

記事リンク

コード

#include <iostream>
#include <list>
using namespace std;

//! 選択ソートテンプレート関数
template <typename InIt, typename Pred>
void select_sort(InIt init, InIt last, Pred pred)
{
    for(InIt curr = init; curr != last; ++curr)
    {
        InIt itMin = curr; 

        // curr 以降のデータ列中で最小の要素を探す
        for(InIt it = curr; it != last; ++it)
        {
            if(pred(*it, *itMin))
            {
                itMin = it;
            }
        }

        // curr と見つかった最小要素の値を交換
        std::swap(*itMin, *curr);
    }
}

// 実行例
int main()
{
    // リストコンテナを定義
    std::list<int> lst = { 5, 4, 8, 7, 9, 1, 0 };

    cout << "最初\n";
    for(int i : lst) { cout << i << ", "; }

    select_sort(lst.begin(), lst.end(),
        [](const int& a, const int& b) -> bool
    {
        // 昇順ソート
        return a < b;
    });

    cout << "\n\n昇順\n";
    for(int i : lst) { cout << i << ", "; }

    select_sort(lst.begin(), lst.end(),
        [](const int& a, const int& b) -> bool
    {
        // 降順ソート
        return a > b;
    });

    cout << "\n\n降順\n";
    for(int i : lst) { cout << i << ", "; }

    return 0;
}

コンソール出力

最初
5, 4, 8, 7, 9, 1, 0, 

昇順
0, 1, 4, 5, 7, 8, 9, 

降順
9, 8, 7, 5, 4, 1, 0, 

メモ

内部で使っているイテレータ itMin をポインタにするともっと早くなるのかなぁ……