【C++】std::sort / partial_sortでコンテナをソート（並べ替え）する方法

2025年9月1日

はじめに

C++でvectorなどのコンテナに格納した要素を、昇順や降順に並べ替えたい（ソートしたい）場面は非常に多くあります。C++の標準ライブラリ <algorithm> には、このための非常に高速で効率的なソート関数が用意されています。

この記事では、代表的な2つのソートアルゴリズムを解説します。

std::sort: 指定した範囲の全ての要素をソートする。
std::partial_sort: 指定した範囲の先頭からN個だけを正しくソートし、残りは順序不定のままにする。

`sort` / `partial_sort` を使ったサンプルコード

このコードは、vectorに格納された点数のリストに対して、まず partial_sort で上位3名の点数を特定し、次に sort で全ての点数を昇順に並べ替えます。

完成コード

#include <iostream>
#include <vector>
#include <algorithm> // sort, partial_sort
#include <iterator>  // next

using namespace std;

// vectorの内容を表示するヘルパー関数
void print_scores(const string& title, const vector<int>& scores) {
    cout << title << ": ";
    for (int score : scores) {
        cout << score << " ";
    }
    cout << endl;
}

int main() {
    vector<int> scores = {75, 92, 58, 100, 84, 65, 95};
    
    print_scores("初期状態", scores);
    cout << "--------------------" << endl;

    // --- 1. partial_sort: 上位3つの点数だけをソート ---
    vector<int> partial_sorted_scores = scores; // コピーを作成
    // 先頭から3つ分の要素が、全体の中で小さい順に3つになるようにソート
    partial_sort(partial_sorted_scores.begin(), 
                 next(partial_sorted_scores.begin(), 3), 
                 partial_sorted_scores.end());
    print_scores("上位3位までをソート (partial_sort)", partial_sorted_scores);

    // --- 2. sort: 全ての要素をソート ---
    vector<int> full_sorted_scores = scores; // コピーを作成
    // 全範囲を昇順にソート
    sort(full_sorted_scores.begin(), full_sorted_scores.end());
    print_scores("全てをソート (sort)", full_sorted_scores);
    
    return 0;
}

実行結果

初期状態: 75 92 58 100 84 65 95 
--------------------
上位3位までをソート (partial_sort): 58 65 75 100 92 84 95 
全てをソート (sort): 58 65 75 84 92 95 100

コードの解説

1. `std::sort`

sort(範囲の開始イテレータ, 範囲の終了イテレータ);

機能: 引数で指定された範囲内の全ての要素を、デフォルトでは昇順に並べ替えます。
パフォーマンス: 非常に効率的なアルゴリズム（イントロソート）が使われており、一般的に極めて高速です。

降順にソートしたい場合は、第3引数に比較オブジェクト greater<int>() を渡します。 sort(scores.begin(), scores.end(), greater<int>());

2. `std::partial_sort`

partial_sort(範囲の開始, ソートしたい範囲の中間, 範囲の終了);

機能: [開始, 終了) の範囲全体の中から、小さい順に [開始, 中間) の範囲に収まるべき要素を探し出し、その [開始, 中間) の区間だけをソート済みの状態にします。[中間, 終了) の残りの要素の順序は不定になります。
next(partial_sorted_scores.begin(), 3): 開始イテレータから3つ進んだ位置のイテレータを取得しています。
使いどころ: ランキングの上位N件だけを知りたい、といった場合に、全要素をソートする sort よりも効率的に動作します。