Какова временная сложность std:: sort() в стандартной библиотеке С++?

Ответ 1

std::sort должна иметь сложную временную сложность среднего порядка (n log n). Любой алгоритм может использоваться при условии, что это требование временной сложности выполнено. Существует не худшее требование временной сложности времени.

Если вы хотите получить гарантированную наихудшую временную сложность, используйте std::stable_sort, у которого есть квазилинейная сложность худшего случая (n log ^ 2 n).

Ответ 2

http://en.wikipedia.org/wiki/Sort_ (C% 2B% 2B)

Конкретный алгоритм сортировки не является обязательным и может варьироваться в разных реализациях. Например, в библиотеке GNU Standard С++ используется гибридный алгоритм сортировки: сначала выполняется интросор, до максимальной глубины, заданной 2 × log2 n, где n - количество элементов, за которым следует сортировка вставки. ] Какая бы ни была реализация, сложность должна быть сравнением O (n log n) в среднем. [2]

Ответ 3

Сложность O(n log n). В некоторых общих реализациях я использую интросорт, насколько мне известно:

http://en.wikipedia.org/wiki/Introsort

Ответ 4

Стандартные гарантии

Из стандарта С++ 11/14 std::sort гарантированно имеет:

§25.4.1.1/3

Сложность: O(N log(N)) (где N == last - first).

Другим, стабильным, стандартным алгоритмом сортировки (а именно std::stable_sort) гарантируется:

25.4.1.2/3

Сложность: она делает не более N log2(N) (где N == last - first); если доступно достаточно дополнительной памяти, это N log(N).

Вместо std::forward_list::stable:

23.3.4.6/26

Сложность: сравнительные сравнения N log(N), где N - distance(begin(), end()).

То же самое относится к std::list:

23.3.5.5/31

Сложность: сравнительные сравнения N log(N), где N == size().

Алгоритм сортировки

В стандарте С++ не указывается, какой алгоритм сортировки применять в любом из перечисленных случаев. Это было бы часто и ненужным ограничением реализации.

Если вам нужно знать, что вам, возможно, повезло в конкретной спецификации компилятора. Например, для GNU GCC вы можете начать здесь.

Ответ 5

Если вы имеете в виду std::sort():

Это из стандарта С++ 03, раздел 25.3. Гарантия исполнения:

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

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

1 Эффекты: Сортирует элементы в диапазоне [первый, последний].

2 Сложность: Приблизительно N log N (где N == последний - первый) сравнения в среднем.