ソートってば期待される結果は極めて単純明快でありながらアルゴリズム次第で実装のややこしさと計算量がドラスティックに変化します。ソートは数理科学の基礎かつキモの一つであり、「アルゴリズムの華」だと思っています。
...とは言いながら、実務でソートを書くことはまずもってありません。多くの場合ライブラリで提供されているものを使えば大抵事足りてしまいますからね。C++においてもそこらへんの事情は同じ、標準C++ライブラリの <algorithm> にはソートおよびソートがらみの関数群が数多く用意されています。
このアーティクルでは標準C++ライブラリの提供するソートをざっくりと眺めてみましょう。
sort: 定番ソートアルゴリズム
その名のとおりのソートです。ランダムアクセス可能なコンテナ、単純に言えば x[n] によって n番目の要素にアクセスできる（例えば配列, array, vectorなどの）コンテナx の要素を昇順（小さい順）に並び替えてくれます。並び順を決定する要素の大小関係は、コンテナの要素 x, y に対し x < y が真であるとき「x は y より小さい」とします。
// 配列, array, vector を昇順にソートする int a[N]; array<int,N> ar; vector<int> v; sort(a, a+N); // 配列 sort(ar.begin(), ar.end()); // array sort(v.begin(), v.end()); // vector
降順（大きい順）にソートしたいとか、シチュエーションに応じてソート・キーを変更したいとか、そんなときにはsort()の第3引数に比較関数オブジェクトを与えます。近頃はラムダ式をサポートする処理系も増えてきたので比較関数オブジェクトを与えるのがずいぶんお手軽になりました。
struct fruit {
string name; // 名前
int price; // 価格
};
vector<fruit> fruits;
// nameをキーに昇順でソート
sort(fruits.begin(), fruits.end(),
[](const fruit& x, const fruit& y) { return x.name < y.name;});
// priceをキーに降順でソート
sort(fruits.begin(), fruits.end(),
[](const fruit& x, const fruit& y) { return x.price > y.price;});
比較関数オブジェクトさえきちんと与えてやればほとんどのソートは sort() でOKです。
sort() ではソートできないケースの一つが、ソート対象であるコンテナがランダム・アクセスでない場合。代表的なのは list, forward_list のソートです。ご心配なく。list, forward_list はメンバ関数 sort() を持っています:
list<fruit> fruits;
// nameをキーに昇順でソート
fruits.sort([](const fruit& x, const fruit& y) { return x.name < y.name;});
// priceをキーに降順でソート
fruits.sort([](const fruit& x, const fruit& y) { return x.price > y.price;});
stable_sort: 安定なソート
ある要素の列をソートしたとき、キーが等しい要素の並び（相対的な位置関係）がソートの前後で狂わないとき、そのソートは"安定である"といいます。例えば期末テストの集計を考えてみます。各要素は出席番号と得点の組であり、元データは出席番号の順に並んでいるものとします。この列を得点をキーに降順でソートするとき、同じ得点の複数の要素に対しソート後においても出席番号順に並んでいてほしいなら、安定なソートでないと困るのね。
ではソートの定番アルゴリズム:sort() が安定であるか調べてみましょう。整数の列:{10,11,12,...,98,99} を一の位をキーに昇順でソートします:
array<int,90> ia;
iota(ia.begin(), ia.end(), 10); // ia = {10,11,12,... }
// 一の位をキーに昇順でソート
sort(ia.begin(), ia.end(), [](int x, int y) { return (x%10) < (y%10);});
for_each(ia.begin(), ia.end(), [](int x) { cout << x << ' ';});
どうやら安定ではなさそうです。安定であるならソート後の要素は 10,20,30,... のようにキレイに並ぶはずですから。
安定なソートがご所望なら stable_sort() をお使いください。インターフェースは sort() とまったく同じ。上記コードの sort() を stable_sort() に置き換えると:
ちなみに、list::sort()、forward_list::sort() は安定です。
