【C++】ソート(std::sort)の使い方：基本の昇順・降順からカスタム順の指定まで解説

C++を用いたアプリケーション開発において、データの集合を特定の規則に従って並び替える「ソート」は、最も頻繁に利用されるアルゴリズムの一つです。

探索の効率化やデータの可視化、統計処理など、ソートが必要となる場面は多岐にわたります。

C++の標準ライブラリ（STL）には、効率的かつ柔軟にソートを実現するための「std::sort」が用意されています。

本記事では、このstd::sortの基本的な使い方から、降順ソート、構造体やクラスを用いたカスタム順序の指定、さらにC++20以降で導入されたより洗練された記法まで、プロフェッショナルの視点で詳細に解説します。

std::sortの基本概念と特徴

C++でソートを行う際、まず検討すべきなのが標準ヘッダ<algorithm>に含まれるstd::sort関数です。

この関数は、非常に高速で汎用性が高いことが特徴です。

std::sortのアルゴリズムと計算量

std::sortの内部アルゴリズムは、多くの場合「イントロソート（Introsort）」と呼ばれるハイブリッドなアルゴリズムで実装されています。

これはクイックソートをベースにしつつ、再帰が深くなりすぎた場合にはヒープソートに切り替え、要素数が少ない場合には挿入ソートを利用することで、最悪の時間計算量をO(N log N)に抑える手法です。

従来のクイックソートでは、データの並び順によっては最悪計算量が $O(N^2)$ に陥るリスクがありましたが、std::sortを使用することで、どのような入力データに対しても安定して高いパフォーマンスを維持できます。

利用できるコンテナ

std::sortを適用できるのは、「ランダムアクセスイテレータ」を提供しているコンテナに限られます。

具体的には、以下のコンテナが該当します。

• std::vector
• std::deque
• 静的配列（C言語スタイルの配列やstd::array）

一方で、std::listやstd::forward_listはランダムアクセスをサポートしていないため、std::sortに渡すことはできません。

これらのコンテナをソートする場合は、メンバ関数としてのlist::sortを利用する必要があります。

基本的なソート（昇順）の使い方

まずは、最も標準的な数値の昇順（小さい順）ソートの方法を確認しましょう。

std::sortの基本的な構文は、ソートしたい範囲の「開始イテレータ」と「終了イテレータ」を引数に渡す形をとります。

数値配列のソート例

以下のプログラムは、std::vector内の整数を昇順にソートする例です。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortに必要

int main() {
    // 未ソートのデータ
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};

    // 昇順にソート (範囲: 開始から終了まで)
    std::sort(numbers.begin(), numbers.end());

    // 結果の出力
    std::cout << "昇順ソート結果: ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

昇順ソート結果: 1 2 5 5 6 9

std::sortに第3引数を与えない場合、要素の比較にはデフォルトでoperator<（未満演算子）が使用されます。

これにより、数値であれば数値の大小、文字列であれば辞書順に並び替えられます。

降順ソートの実装方法

データを大きい順（降順）に並べ替えたい場合、いくつかの方法があります。

代表的なのは、標準ライブラリの比較関数オブジェクトを使用する方法と、ラムダ式を使用する方法です。

std::greaterを利用する方法

C++には、大小比較を行うための標準的なファンクタ（関数オブジェクト）が用意されています。

<functional>ヘッダをインクルードし、std::greater<T>()を第3引数に指定することで、簡単に降順ソートを実現できます。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // std::greaterに必要

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};

    // std::greaterを指定して降順にソート
    std::sort(numbers.begin(), numbers.end(), std::greater<int>());

    std::cout << "降順ソート結果: ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

降順ソート結果: 9 6 5 5 2 1

ラムダ式を利用する方法

C++11以降、ラムダ式（無名関数）を用いることで、その場に比較ロジックを記述できるようになりました。

柔軟性が高く、降順ソート以外にも複雑な条件を記述する際に非常に便利です。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};

    // ラムダ式による降順ソート
    // 第1引数が第2引数より大きければ true を返すように定義
    std::sort(numbers.begin(), numbers.end(), [](int a, int b) {
        return a > b;
    });

    std::cout << "ラムダ式による降順結果: ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

ラムダ式による降順結果: 9 6 5 5 2 1

カスタム順序の指定（構造体・クラスのソート）

実務においては、単純な数値だけでなく、複数のメンバを持つ構造体やクラスのオブジェクトをソートする場面が多くあります。

例えば、学生の「ID」と「スコア」を持つ構造体を、スコアが高い順に並べ替えるといったケースです。

比較関数の定義

カスタムソートを実現するには、std::sortの第3引数に比較用の関数や関数オブジェクトを渡します。

比較関数は、「Strict Weak Ordering（狭義の弱順序）」のルールに従う必要があります。

具体的には、「aがbより前に来るべきなら true、そうでなければ false を返す」という論理で記述します。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct Student {
    int id;
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {1, "Alice", 85},
        {2, "Bob", 92},
        {3, "Charlie", 78},
        {4, "Dave", 92}
    };

    // スコアの降順でソートし、スコアが同じならIDの昇順にする
    std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) {
            return a.score > b.score; // スコアが高い順
        }
        return a.id < b.id; // スコアが同じならIDが小さい順
    });

    std::cout << "学生ランキング:" << std::endl;
    for (const auto& s : students) {
        std::cout << "ID: " << s.id << ", Name: " << s.name << ", Score: " << s.score << std::endl;
    }

    return 0;
}

学生ランキング:
ID: 2, Name: Bob, Score: 92
ID: 4, Name: Dave, Score: 92
ID: 1, Name: Alice, Score: 85
ID: 3, Name: Charlie, Score: 78

演算子オーバーロードによる定義

クラス自体にデフォルトの順序を持たせたい場合は、operator<をオーバーロードします。

これにより、第3引数を省略した際にも自作クラスのソートが可能になります。

struct Point {
    int x, y;
    // x座標で比較、xが同じならy座標で比較
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

std::stable_sortによる安定ソート

標準のstd::sortは、ソートアルゴリズムの性質上、「同等の値を持つ要素の相対的な順序」を維持することを保証しません。

これを「不安定なソート」と呼びます。

一方、「安定ソート（Stable Sort）」が必要な場合は、std::stable_sortを使用します。

安定ソートが必要なケース

例えば、「まず名前順でソートされているリスト」を、後から「スコア順」でソートし直したいとします。

安定ソートを使用すれば、同じスコアを持つ人同士の間では、以前の「名前順」が保持されます。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct Item {
    std::string category;
    int price;
};

int main() {
    std::vector<Item> items = {
        {"Fruit", 100},
        {"Drink", 150},
        {"Fruit", 80},
        {"Drink", 100}
    };

    // std::stable_sort を使用
    std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.price < b.price;
    });

    for (const auto& item : items) {
        std::cout << item.category << ": " << item.price << std::endl;
    }

    return 0;
}

std::stable_sortは通常、マージソートをベースに実装されており、メモリに余裕がある場合は $O(N \log N)$ 、メモリが制限されている場合は $O(N (\log N)^2)$ の計算量となります。

C++20 Rangesによるモダンなソート

C++20からは「Rangesライブラリ」が導入され、ソートの記法が大幅に簡略化・強化されました。

従来のstd::sort(v.begin(), v.end())のようにイテレータをペアで渡す必要がなくなり、コンテナそのものを渡すことができるようになっています。

std::ranges::sort の基本

<algorithm>ヘッダ内のstd::ranges::sortを使用します。

#include <iostream>
#include <vector>
#include <algorithm> // ranges::sortに必要

int main() {
    std::vector<int> numbers = {3, 1, 4, 1, 5, 9};

    // イテレータではなく、コンテナを直接渡せる
    std::ranges::sort(numbers);

    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

プロジェクション（Projection）の活用

C++20のソートで最も強力な機能の一つが「プロジェクション」です。

これは、「どのメンバ変数に基づいて比較するか」を個別に指定できる仕組みです。

従来のラムダ式による比較よりも簡潔に記述できます。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    // age メンバを基準にソートすることを指定
    // 第2引数に比較演算（省略可）、第3引数にプロジェクション（メンバポインタなど）を渡す
    std::ranges::sort(people, {}, &Person::age);

    for (const auto& p : people) {
        std::cout << p.name << " (" << p.age << ")" << std::endl;
    }

    return 0;
}

プロジェクションを使うことで、[](const Person& a, const Person& b) { return a.age < b.age; } という冗長な記述を避けることができ、コードの意図がより明確になります。

特定の条件でのソート：部分ソートと要素選択

全要素をソートする必要がなく、上位数件だけが必要な場合、std::sortを使うのは計算資源の無駄になることがあります。

C++にはそのようなケースに最適なアルゴリズムも用意されています。

std::partial_sort

「上位N件だけを完全にソートして取得したい」場合に適しています。

// 最初の3要素だけを最小値から順に並べる
std::partial_sort(v.begin(), v.begin() + 3, v.end());

std::nth_element

「上位N件（順不同）とそれ以外に分けたい」場合や「中央値を取得したい」場合に非常に高速です。

// 5番目に小さい要素を v.begin() + 4 の位置に配置する
// その左側には5番目より小さい要素、右側には大きい要素が集まる（順序は未保証）
std::nth_element(v.begin(), v.begin() + 4, v.end());

これらは全ソートよりも計算コストが低いため、大規模なデータを扱う際には重要な選択肢となります。

ソート使用時の注意点とベストプラクティス

std::sortを安全かつ効率的に使用するために、以下の点に注意してください。

1. 比較関数の整合性（Strict Weak Ordering）

比較関数を自作する場合、以下の条件を満たさなければなりません。

• 非反射性: a < a は常に false。
• 非対称性: a < b が true なら、b < a は必ず false。
• 推移性:</bold> a < b かつ b < c なら、a < c は true。

特に「a < b」を記述すべき箇所で「a <= b」のように等号を含めてしまうと、プログラムがクラッシュしたり無限ループに陥ったりする原因となります。

必ず「未満」の論理で実装してください。

2. コンテナの選択

前述の通り、std::sortはランダムアクセスイテレータを要求します。

• std::vector や std::array は std::sort を使用する。
• std::list や std::forward_list は独自の .sort() メンバ関数を使用する。
• ソート済みの状態を常に維持したい場合は、std::set や std::map の利用を検討する。

3. パフォーマンス最適化

要素のコピーコストが高い大きな構造体をソートする場合、ポインタやインデックスの配列をソートするか、std::moveを活用するように設計することで、パフォーマンスの低下を防ぐことができます。

また、C++17以降であれば、実行ポリシー（std::execution::par）を指定することで、並列ソートを行うことも可能です。

#include <execution>
// 並列ソートの例
std::sort(std::execution::par, v.begin(), v.end());

まとめ

C++のstd::sortは、非常に強力かつ柔軟なツールです。

基本的な数値の昇順ソートから、ラムダ式を用いた複雑な条件指定、そしてC++20 Rangesによる洗練されたプロジェクションまで、その活用範囲は非常に広いです。

本記事で解説した以下のポイントを意識することで、より高品質なコードを記述できるようになります。

• 基本はstd::sortを使用し、必要に応じてstd::stable_sortを選択する。
• カスタムソートにはラムダ式やC++20のプロジェクションを活用して記述を簡潔に保つ。
• 比較関数では「Strict Weak Ordering」を厳守し、バグの混入を防ぐ。
• 計算量やコンテナの特性を理解し、最適なアルゴリズム（partial_sortなど）を使い分ける。

これらの知識を土台に、実際の開発現場で最適なソート処理を実装していきましょう。