Какой тип сортировки используется в std:: sort()?

Ответ 1

В большинстве реализаций std::sort используется quicksort (или обычно гибридный алгоритм, такой как introsort, который объединяет сортировку quicksort, heapsort и insertion).

Единственное, что требуется стандарту, это то, что std::sort каким-то образом сортирует данные в соответствии с указанным порядком со сложностью приблизительно O (N log (N)); не гарантируется стабильность. Технически, introsort лучше отвечает требованиям сложности, чем quicksort, поскольку quicksort имеет квадратичное худшее время.

Ответ 2

Стандарт С++ ISO/IEC 14882: 2003

25.3.1.1 сортировка

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 == последний - первые) сравнения в среднем.

Информация о методе отсутствует, но сложность всегда N log N.

Ответ 3

Существует три алгоритма, которые используются в STL MSVC2013, ссылаясь на исходный код std::sort.

Скорее всего, он будет использовать QuickSort или вариант с QuickSort, называемый IntroSort.

Если рекурсия идет слишком глубоко, здесь будет использоваться HeapSort.

В противном случае будет использоваться InsertSort.

Ответ 4

Вероятно, во всех реализациях std::sort используется introsort (aka introspection sort), гибридный алгоритм, который объединяет quicksort и heapsort. На самом деле, интросорт был особенно изобретен в 1997 году с целью реализации исполнительского сорта в С++ STL.

Единственное, что требуется стандарту, это то, что std::sort каким-то образом сортирует данные в соответствии с указанным порядком со сложностью O (N log (N)); он не гарантированно стабилен (существуют отдельные алгоритмы std::stable_sort, если это необходимо).

Технически, introsort лучше отвечает требованиям сложности, чем quicksort: это потому, что heapsort гарантировал сложность O (N log (N)) в худшем случае, тогда как quicksort имеет квадратичное худшее время.

Однако в среднем случае heapsort "медленнее", чем quicksort, в том смысле, что heapsort выполняет C * N log (N), тогда как quicksort имеет производительность D * N log (n), при этом D значительно меньше C ( числа C и D - константы). Другими словами, накладные расходы по сравнению с предыдущим объемом выше, чем у быстрой сортировки.

Чтобы получить лучшее из обоих миров, introsort начинается с quicksort-рекурсивного алгоритма, но когда глубина рекурсии становится слишком высокой (что означает, что она попадает в вырожденное худшее поведение), она переключается на heapsort.

См. также запись в Wikipedia для introsort или оригинальная бумага от Дэвида Муссера, который изобрел интросорт, особенно для STL.

Ответ 5

Вы имеете в виду std:: sort? Если так, то это может быть реализовано любым способом. Вероятно, это Quick sort, но может быть radix или что-то еще. Пока он производит вам отсортированный список, по крайней мере, в O (n log n), реализация в порядке, afaik.

Ответ 6

Только некоторые эмпирические результаты:

Я перевел python script, используя numpy 1.9.2 sort to С++, используя std:: sort (VS2008 toolchain).

Я получаю только точные точные результаты на сторонах python и С++, когда я использую аргумент numpy.sort kind = 'mergesort'. Я получаю разные относительные упорядочения для элементов с одним ключом, когда kind = 'quicksort' или kind = 'heapsort'. Поэтому я предполагаю, что по крайней мере для версии STL, которая поставляется с VS2008, std:: sort использует mergesort.