C++ 標準テンプレートライブラリ（STL）での並べ替え方法

C++ 標準ライブラリの <algorithm> の sort() 関数を使って、配列またはベクトルをその場で並べ替えます。デフォルトでは、first から last の直前までの半開範囲を昇順に並べ替えます。別の順序を選ぶには比較関数を渡します。

sort() 関数を使って C++ で配列またはベクトルを並べ替える

std::sort はランダムアクセス イテレータを受け入れるため、配列とベクトルで動作します。std::set や std::map はランダムアクセス イテレータを提供しないため、その場で並べ替えることはできません。この完全なプログラムは、配列とベクトルの両方を並べ替えます。

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

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin と std::end は配列の範囲を提供し、ベクトルはその begin() イテレータと end() イテレータを使います。このプログラムは未実行の例として提供されており、その出力は、構成された実行環境で観測されるまで省略されます。両方の呼び出しは元の要素を変更するため、後のコードは新しい順序でそれらを参照します。コンテナの一部だけを並べ替えるには、その部分を区切るイテレータを渡します。

C++ で配列またはベクトルを降順に並べ替える

std::greater<> を 3 番目の引数として渡すと、値が大きいものから小さいものへ並べ替えられます。比較関数のために <functional> をインクルードしてください。たとえば、std::sort(values.begin(), values.end(), std::greater<>{}); はベクトルを降順に並べ替えます。比較関数は、並べ替える範囲を変えずに、順序の規則を変更します。

partial_sort() を使って配列またはベクトルの一部を並べ替える

プレフィックスだけを並べ替えればよい場合は partial_sort(first, middle, last) を使います。これは、最も小さい middle - first 個の要素を並べ替えた順序で middle の前に配置します。middle から last までの要素には特定の順序は保証されません。たとえば、std::partial_sort(values.begin(), values.begin() + 3, values.end()); は、最初の 3 つの位置に対して最も小さい 3 つの値を選択します。

C++ で sort() にカスタム比較関数を使う

比較関数を使用すると、文字列の長さのようなキーで値を並べ替えることができます。たとえば、std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); は短い文字列を先に配置します。比較関数は厳密な弱順序を定義しなければなりません。一貫性があり、アイテムがそれ自体に先行すると見なしてはなりません。長さが等しい文字列はこの比較では等価であるため、その相対的な順序は未規定です。この例を使うときは、<algorithm> と一緒に <string> をインクルードしてください。

is_sorted() で範囲が並べ替えられているか確認する

std::is_sorted(first, last) は、first から last の直前までの範囲がデフォルトの比較に従って順序付けられている場合は true を、そうでない場合は false を返します。要素を並べ替えることなく範囲を確認します。カスタムの順序を確認する場合は、その順序に使ったのと同じ比較関数を指定してください。例：std::is_sorted(words.begin(), words.end(), compare)。

並べ替えアルゴリズムの時間計算量

std::sort について、標準では最悪の場合 O(N log N) 回の比較が規定されています。ここで N は範囲内の要素数です。これは、範囲の長さに応じて作業量がどのように増えるかを示すものであり、特定の並べ替え実装を約束するものではありません。std::partial_sort は、N 個から K 個の要素を選択して並べ替える際に約 N log K 回の比較を使用し、std::is_sorted は最大で N - 1 回の比較を行います。これらの上限は、範囲を完全に並べ替えることと、プレフィックスだけを並べ替えること、または既存の順序を確認することとを区別するのに役立ちます。