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

Question

Может кто-нибудь сказать, пожалуйста, какой метод сортировки (пузырьковая, вставка, выделение, быстрый, слияние, счет ...) реализован в функции std::sort(), определенной в заголовочном файле <algorithm>?

Answer 1

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

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

Answer 2

C ++ Стандарт 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.

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

Я перевел скрипт Python, используя numpy 1.9.2 sort, в C ++, используя std :: sort (VS2008 toolchain).

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

Answer 6

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