実行できるC++ドキュメント: ソート

Q: C++でベクタをソートするにはどうすればよいですか?

をインクルードしてsort(v.begin(), v.end())を呼び出します。これはoperator<を使って要素をその場で昇順にソートします。配列をソートするには、arrとarr + n（またはbegin(arr) / end(arr)）を渡します。

Q: C++で降順にソートするにはどうすればよいですか?

a > bを返す比較関数を渡します: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });。 にある組み込みのsort(v.begin(), v.end(), greater ());を使うこともできます。

Q: なぜ私の比較関数はC++でstd::sortをクラッシュさせるのですか?

比較関数は狭義の弱順序（strict weak ordering）でなければなりません。つまり、両方の引数が等しいときはfalseを返す必要があります。 =を使うと（等しい要素に対してtrueを返すため）このルールが破られ、未定義動作になります。std::sortが範囲外を読み取ってクラッシュすることがあります。必ず で比較してください。

ソートもまた一つのアルゴリズムにすぎない

前のページでは、標準ライブラリがイテレータを通じて任意の範囲に対して動作する、すぐに使えるアルゴリズムを備えていることを見ました。ソートはその中でも最も頻繁に使うものであり、独立したページを設けているのは、いくつかの鋭い落とし穴があるからです。カスタムの順序、安定性、そして破ると間違った答えではなく未定義動作を返してくるルールです。

主役は<algorithm>のstd::sortです。範囲の先頭と末尾を渡すと、要素をその場で昇順に並べ替えます:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // 昇順、その場で

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

コピーは作られません。ベクタそのものが並べ替えられます。内部的にはstd::sortは通常イントロソート（ヒープソートにフォールバックするクイックソート）であり、平均でO(n log n)を実現します。これはほぼ常に、自前のソートを書くよりも速く、はるかにバグが入りにくいです。

素のC配列に対しても動作します。範囲をポインタで記述するだけです:

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

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // または sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

比較関数によるカスタム順序

デフォルトではstd::sortはoperator<で要素を順序付けます。別の順序でソートするには、第3引数を渡します。2つの要素を受け取り、最初の要素が2番目より前に来るべきならtrueを返す比較関数です。

ラムダが自然な選択です。降順は単にa > bです:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // aが大きいとき「aがbより前」-> 降順
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

組み込み型に対する単純な降順というよくあるケースのために、ライブラリは<functional>に既製の比較関数greater<T>()まで用意しています:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // a > b と同じ

比較関数は、値そのもの以外の基準でソートする方法でもあります。たとえば、文字列をアルファベット順ではなく長さでソートする場合です:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // 短い単語を先に
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

数バイトより大きいもの（stringなど）については、比較関数のパラメータをconst&で受け取りましょう。比較のたびに各要素をコピーするのは完全な無駄です。

構造体をフィールドでソートする

実際のプログラムでは、通常、構造体のコレクションをそのフィールドの一つでソートします。比較関数は、注目しているフィールドにアクセスするだけです。ここでは人々を年齢順に、若い順にソートします:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

LinusとDennisがどちらも25歳であることに注目してください。ここでは元の相対順序のまま出力されましたが、std::sortはそれを保証しません。等しい要素の相対順序が重要な場合は、それを保持するstd::stable_sortを使います（わずかな性能コストはかかります）:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // LinusはDennisより前のまま - 入力順が保持される
    return 0;
}

意図的にタイ（同点）を解決するには（たとえば年齢でソートし、その次に名前のアルファベット順にする）、主キーが等しいときだけ副キーを比較します。std::tieを使えばこれがすっきり書けます:

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // 年齢、次に名前
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // DennisとLinusは25、アルファベット順
    return 0;
}

狭義の弱順序の落とし穴

これはC++のソートにおいて最も危険なミスです。なぜなら、間違った答えを返すのではなく、未定義動作を返すからです。それはしばしばクラッシュや範囲外読み取りを意味します。

std::sortは、比較関数が狭義の弱順序を定義することを要求します。実用的なルール: 任意の要素xについて**comp(x, x)はfalseでなければならない**。言い換えれば、ある要素は決して自分自身より「前」にはなりません。それこそが<や>が与えてくれるもので、<=や>=が破ってしまうものです:

// バグ: a == b のとき true を返し、狭義の弱順序に違反する。
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // 未定義動作 - 一部の入力でクラッシュすることがある
});

<=を使うと、比較関数は5が別の5より前に来ると主張することになり、これは矛盾しています。するとstd::sortはポインタを範囲の末尾を超えて進めてしまうことがあります。小さな入力では一見動いてしまうことがあり、それがこのバグを恐ろしいものにしています。テストを通過しても本番でクラッシュしかねないのです。修正は単純に<です:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // 正しい: 等しいとき false
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

2つ目の典型的な落とし穴: ソートは、その範囲を指しているものすべてを無効にします。 ソート前に保存しておいたイテレータ、ポインタ、インデックスは、要素が移動したため、後では同じ論理的な要素を指さなくなります。必要な位置はソートの後に求め直してください。決して前ではありません。

範囲の一部だけをソートする

ときには全部をソートする必要はなく、上位のいくつかだけが欲しいことがあります。先頭の3つを読むためにベクタ全体をソートするのは無駄です。std::partial_sortは要求した要素だけを並べ、残りは未規定の順序のまま残すため、より低コストです:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // 最小の3つを順に先頭へ。残りは未規定。
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

そして、ある位置に来るはずの唯一の要素（中央値など）だけが必要なら、std::nth_elementはさらに少ない作業で済みます。正しい要素をそのインデックスに配置し、それより小さいものはすべて前に、大きいものはすべて後ろに置きます。すべて平均O(n)です。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

「完全にソート」が問題が実際に必要とする以上である場合は、これらを使いましょう。大きなデータでは実際の時間を節約できます。

次へ: テンプレート

同じstd::sortがint、string、そしてあなた自身のPerson構造体を扱えて、greater<int>()が同じくらい簡単にgreater<string>()にもなり得たことに気づきましたか? その汎用性は魔法ではありません。それがテンプレートであり、呼び出し側が差し込む任意の型に対して一つのコードを動作させる仕組みです。次のページでは、あなた自身のテンプレート化された関数やクラスの書き方を見ていきます。そうすれば、あなたのコードも、これまで使ってきたアルゴリズムと同じくらい型に依存しないものにできます。

よくある質問

C++でベクタをソートするにはどうすればよいですか?

<algorithm>をインクルードしてsort(v.begin(), v.end())を呼び出します。これはoperator<を使って要素をその場で昇順にソートします。配列をソートするには、arrとarr + n（またはbegin(arr) / end(arr)）を渡します。

C++で降順にソートするにはどうすればよいですか?

a > bを返す比較関数を渡します: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });。<functional>にある組み込みのsort(v.begin(), v.end(), greater<int>());を使うこともできます。

なぜ私の比較関数はC++でstd::sortをクラッシュさせるのですか?

比較関数は**狭義の弱順序（strict weak ordering）**でなければなりません。つまり、両方の引数が等しいときはfalseを返す必要があります。<=や>=を使うと（等しい要素に対してtrueを返すため）このルールが破られ、未定義動作になります。std::sortが範囲外を読み取ってクラッシュすることがあります。必ず<または>で比較してください。