「入れ替えを行わないソート」のおはなし

　今回のお題は「ソート」です――なにをいまさらソートなんか、ではありますけど、先日少々変則的なソートを実装する必要に迫られ、プログラミングのトピックとして面白いんじゃないかと取り上げることにしました。要素の順序を入れ替えないソートのおはなしです。

標準の関数によるソート

　ソートそのものを自前で実装したのは数年前にやったきり。きょう日ほとんどの言語でライブラリ内に用意されているので、よっぽどのことがない限り自作することはなくなりましたよね（プログラミングの練習問題にはよく出てきます。代入・比較・交換・繰り返しなど、プログラミングの"いろは"が詰まってますからね）。

　標準C++のソート関数std::sortの使い方はとっても簡単、ソート対象となる配列／vector／dequeなどの要素列の先頭と末尾（の直後）とを引数に与えるだけで、要素a, bに対しa < bならばaがbより列の先頭に近い位置に置かれるよう（つまり昇順／小さい順）にソートされます。部分ソートstd::partial_sortや安定なソートstd::stable_sortも同様です。

list-01

// data[N] を昇順にソートする
double data[N];
std::sort(data, data+N);
// あるいは
// std::sort(std::begin(data), std::end(data));

　std::sortには第3引数に要素の並び順を判定する関数オブジェクトを与えることができます。関数オブジェクトは2つの要素a, bを引数として呼び出され、そのときにtrueを返せばaはbより先頭寄りに配置されます。

list-02

// 降順にソートする
double data[N];
sort(begin(data), end(data), [](double a, double b) { return b < a; });

list-03

// 文字列長の短い順にソートする
string data[N];
sort(begin(data), end(data), 
    [](const string& a, const string& b) {
      return a.length() < b.length(); });