std::sort

Определено в заголовочном файле `<algorithm>`
template< class RandomIt > void sort( RandomIt first, RandomIt last );	(1)	(constexpr с C++20)
template< class ExecutionPolicy, class RandomIt > void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(с C++17)
template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp );	(3)	(constexpr с C++20)
template< class ExecutionPolicy, class RandomIt, class Compare > void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );	(4)	(с C++17)

Сортирует элементы в диапазоне [first, last) в неубывающем порядке. Порядок эквивалентных элементов не гарантируется.

1) Элементы сортируются относительно operator<(до C++20)std::less{}(с C++20).

3) Элементы сортируются относительно comp.

2,4) Аналогично (1,3), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(с C++20)

Если выполняется любое из следующих условий, поведение не определено:

Тип `*first` не удовлетворяет требованиям Swappable.	(до C++11)
`RandomIt` не удовлетворяет требованиям ValueSwappable. Тип `first` не удовлетворяет требованиям MoveConstructible. Тип `first` не удовлетворяет требованиям MoveAssignable.	(с C++11)

Параметры

first, last	-	пара итераторов, задающих диапазон сортируемых элементов
policy	-	политика выполнения
comp	-	объект функции сравнения (то есть объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго (то есть расположен перед ним). Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&b); Хотя сигнатура не обязана содержать const&, функция не должна изменять переданные ей объекты и должна принимать значения любого типа (возможно, константные) `Type1` и `Type2` независимо от категории значения (таким образом, `Type1&` недопустимо, как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt можно было разыменовать и неявно преобразовать к каждому из них.
Требования к типам
-`RandomIt` должен удовлетворять требованиям LegacyRandomAccessIterator.
-`Compare` должен удовлетворять требованиям Compare.

Сложность

Пусть \(\scriptsize N\)N — это last - first:

1,2) \(\scriptsize O(N \cdot \log(N))\)O(N·log(N)) сравнений с использованием operator<(до C++20)std::less{}(с C++20).

3,4) \(\scriptsize O(N \cdot \log(N))\)O(N·log(N)) вызовов компаратора comp.

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной в рамках алгоритма, приводит к исключению и ExecutionPolicy — одна из стандартных политик, вызывается std::terminate. Для любого другого ExecutionPolicy поведение определяется реализацией.
Если алгоритму не удаётся выделить память, выбрасывается std::bad_alloc.

Возможная реализация

См. также реализации в libstdc++ и libc++.

Примечания

До принятия LWG713 требование к сложности допускало реализацию sort() только с помощью быстрой сортировки, которой в худшем случае может потребоваться \(\scriptsize O(N^2)\)O(N²) сравнений.

Интросортировка обрабатывает все случаи за \(\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++.

Отчёт о дефекте	Применён к	Опубликованное поведение	Корректное поведение
LWG 713	C++98	временная сложность \(\scriptsize O(N \cdot \log(N))\)O(N·log(N)) требовалась только в среднем случае	она требуется для худшего случая

См. также

partial_sort	сортирует первые N элементов диапазона (шаблон функции и функциональный объект алгоритма)
ranges::partial_sort (C++20)
stable_sort	сортирует диапазон элементов, сохраняя взаимный порядок эквивалентных элементов (шаблон функции и функциональный объект алгоритма)
ranges::stable_sort (C++20)
sort	сортирует элементы (открытая функция-член `std::list<T,Allocator>`)
sort	сортирует элементы (открытая функция-член `std::forward_list<T,Allocator>`)
sort	сортирует элементы (открытая функция-член `std::hive<T,Allocator>`)
ranges::sort (C++20)	сортирует диапазон элементов (функциональный объект алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/sort