Какие алгоритмы используются в C++11 std::sort в разных реализациях STL?

Стандарт C++11 гарантирует, что std::sort имеет сложность O(n logn) в худшем случае. Это отличается от гарантии среднего случая в C++98/03, где std::sort может быть реализовано с помощью быстрой сортировки (может быть объединено с сортировкой вставки для малых n), которая имеет O(n^2) в худшем случае (для некоторого конкретного ввода, такого как сортированный ввод).

Были ли какие-либо изменения в std::sort реализации в разных библиотеках STL? Как С ++ 11 std::sort реализованы в разных STL?

Источник

2 ответа

Решение

Просматривая онлайн-источники для libstdC++ и libC++, можно увидеть, что обе библиотеки используют полную гамму известных алгоритмов сортировки из основного цикла intro-sort:

За std::sortесть вспомогательная рутина для insertion_sort (O(N^2) алгоритм, но с хорошей константой масштабирования, чтобы сделать его конкурентоспособным для небольших последовательностей), а также специальный корпус для подпоследовательностей из 0, 1, 2 и 3 элементов.

За std::partial_sortобе библиотеки используют версию heap_sort (O(N log N) в общем), потому что этот метод имеет хороший инвариант, что он сохраняет отсортированную подпоследовательность (обычно он имеет большую константу масштабирования, чтобы сделать его более дорогим для полной сортировки).

За std::nth_elementесть вспомогательная рутина для selection_sort (снова алгоритм O(N^2) с хорошей постоянной сглаживания, чтобы сделать его конкурентоспособным для небольших последовательностей). Для регулярной сортировки insertion_sort обычно доминирует selection_sort, но для nth_element инвариант наличия наименьших элементов идеально соответствует поведению selection_sort,

Источник

Вопрос в том, как STL может сказать std::sort в худшем случае это O(N log(N)), хотя по сути это QuickSort. STL сортируется по типу IntroSort. IntroSort - это, по сути, QuickSort, разница, внесенная, меняет сложность наихудшего случая.

QuickSort худший случай O(N^2)

Какое бы разбиение вы ни выбрали, существует последовательность, которую QuickSort будет запускать на O(N^2). Выбранное вами разделение только уменьшает вероятность возникновения наихудшего случая. ( Случайный выбор точки разворота, медиана-три и т. Д.)

РЕДАКТИРОВАТЬ: Благодаря коррекции @maxim1000 с. Быстрая сортировка с алгоритмом выбора сводных значений Median of Medians имеет O(N log(N)) сложность в худшем случае, но из-за накладных расходов, которые она представляет, она не используется на практике. Он показывает, насколько хороший алгоритм выбора теоретически может изменить сложность наихудшего случая с помощью кругового выбора.

Что делает IntroSort?

IntroSort ограничивает ветвление QuickSort. Это самый важный момент, этот предел составляет 2 * (log N). Когда предел достигнут, IntroSort может использовать любой алгоритм сортировки, который имеет наихудшую сложность O(N log(N)).

Ветвление прекращается, когда у нас есть O(log N) подзадач. Мы можем решить любую подзадачу O(n log n). (Нижний регистр n обозначает размеры подзадачи).

Сумма (n log n) - наша сложность в худшем случае.

Для наихудшего случая быстрой сортировки; Предположим, у нас уже есть отсортированный массив, и мы всегда выбираем первый элемент в этом массиве в качестве оси. В каждой итерации мы избавляемся только от первого элемента. Если бы мы пошли этим путем до конца, это был бы O(N^2), очевидно. С IntroSort мы останавливаем QuickSort, когда мы достигаем глубины журнала (N), затем мы используем HeapSort для оставшегося несортированного массива.

16 -> 1  /**N**/
   \
    > 15 -> 1 /**N - 1**/
         \
          > 14 -> 1 /**N - 2**/
               \
                > 13 -> 1 /**N - log(N)**/  
                     \
                      > 12 /**(HeapSort Now) (N - log(N)) log (N - log(N))**/

Подведите их итог;

До прекращения ветвления, N + (N - 1) + ... + (N - log(N)) Операции выполнены. Вместо того, чтобы использовать гаусс, чтобы подвести итог, мы можем просто сказать, N + (N - 1) + ... + (N - log(N)) < N log(N),

Часть HeapSort является (N - log(N)) log(N - log(N)) < N log(N)

Общая сложность < 2 N log(N),

Поскольку константы могут быть опущены, сложность IntroSort в наихудшем случае равна O(N log(N)).

Дополнительная информация: исходный код реализации GCC STL находится здесь. Sort функция находится на линии 5461.

Исправление: * Microsoft.NET * sort Внедрение IntroSort с 2012 года. Соответствующая информация здесь.

Источник
Другие вопросы по тегам