std::sort

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last, Compare comp );

範囲 [first, last) 内の要素を非降順にソートします。等しい要素の順序は保持されることは保証されません。

次の条件のいずれかが満たされる場合、動作は未定義です:

パラメータ

計算量

\(\scriptsize N\) N が last - first として与えられる：

例外

ExecutionPolicyという名前のテンプレートパラメータを持つオーバーロードは、 以下のようにエラーを報告します：

• アルゴリズムの一部として呼び出された関数の実行が例外をスローした場合、 ExecutionPolicy が 標準ポリシー のいずれかであるとき、 std::terminate が呼び出される。それ以外の ExecutionPolicy については、動作は実装定義である。
• アルゴリズムがメモリの確保に失敗した場合、 std::bad_alloc がスローされる。

実装例

実装については libstdc++ および libc++ も参照してください。

注記

LWG713以前は、計算量要件により LWG713 の実装が Quicksort のみを使用することを許可しており、最悪の場合 \(\scriptsize O(N^2)\) O(N 2
) 回の比較が必要となる可能性がありました。

Introsort はすべてのケースを \(\scriptsize O(N \cdot \log(N))\) O(N·log(N)) 回の比較で処理でき（平均ケースで追加のオーバーヘッドを発生させない）、したがって通常 sort() の実装に使用されます。

libc++は、修正された時間計算量の要件を LLVM 14まで 実装していません。

例

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <string_view>
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    auto print = [&s](std::string_view const rem)
    {
        for (auto a : s)
            std::cout << a << ' ';
        std::cout << ": " << rem << '\n';
    };
    std::sort(s.begin(), s.end());
    print("sorted with the default operator<");
    std::sort(s.begin(), s.end(), std::greater<int>());
    print("sorted with the standard library compare function object");
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    }
    customLess;
    std::sort(s.begin(), s.end(), customLess);
    print("sorted with a custom function object");
    std::sort(s.begin(), s.end(), [](int a, int b)
                                  {
                                      return a > b;
                                  });
    print("sorted with a lambda expression");
}

0 1 2 3 4 5 6 7 8 9 : sorted with the default operator<
9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object
0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object
9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

関連項目